Source code

001/*
002 * $Id: PrimeList.java 4940 2014-10-05 13:34:52Z axelclk $
003 */
004
005package edu.jas.arith;
006
007
008// import java.util.Random;
009import java.util.ArrayList;
010import java.util.Iterator;
011import java.util.List;
012
013
014/**
015 * List of big primes. Provides an Iterator for generating prime numbers.
016 * Similar to ALDES/SAC2 SACPOL.PRIME list.
017 * 
018 * @author Heinz Kredel See Knuth vol 2,page 390, for list of known primes. See
019 *         also ALDES/SAC2 SACPOL.PRIME
020 */
021
022public final class PrimeList implements Iterable<java.math.BigInteger> {
023
024
025    /**
026     * Range of probable primes.
027     */
028    public static enum Range {
029        small, low, medium, large, mersenne
030    };
031
032
033    /**
034     * Cache the val list for different size
035     */
036    private volatile static List<java.math.BigInteger> SMALL_LIST = null;
037
038
039    private volatile static List<java.math.BigInteger> LOW_LIST = null;
040
041
042    private volatile static List<java.math.BigInteger> MEDIUM_LIST = null;
043
044
045    private volatile static List<java.math.BigInteger> LARGE_LIST = null;
046
047
048    private volatile static List<java.math.BigInteger> MERSENNE_LIST = null;
049
050
051    /**
052     * The list of probable primes in requested range.
053     */
054    private List<java.math.BigInteger> val = null;
055
056
057    /**
058     * The last prime in the list.
059     */
060    private java.math.BigInteger last;
061
062
063    /**
064     * Constructor for PrimeList.
065     */
066    public PrimeList() {
067        this(Range.medium);
068    }
069
070
071    /**
072     * Constructor for PrimeList.
073     * 
074     * @param r size range for primes.
075     */
076    public PrimeList(Range r) {
077        // initialize with some known primes, see knuth (2,390)
078        switch (r) {
079        case small:
080            if (SMALL_LIST != null) {
081                val = SMALL_LIST;
082            } else {
083                val = new ArrayList<java.math.BigInteger>(50);
084                addSmall();
085                SMALL_LIST = val;
086            }
087            break;
088        case low:
089            if (LOW_LIST != null) {
090                val = LOW_LIST;
091            } else {
092                val = new ArrayList<java.math.BigInteger>(50);
093                addLow();
094                LOW_LIST = val;
095            }
096            break;
097        default:
098        case medium:
099            if (MEDIUM_LIST != null) {
100                val = MEDIUM_LIST;
101            } else {
102                val = new ArrayList<java.math.BigInteger>(50);
103                addMedium();
104                MEDIUM_LIST = val;
105            }
106            break;
107        case large:
108            if (LARGE_LIST != null) {
109                val = LARGE_LIST;
110            } else {
111                val = new ArrayList<java.math.BigInteger>(50);
112                addLarge();
113                LARGE_LIST = val;
114            }
115            break;
116        case mersenne:
117            if (MERSENNE_LIST != null) {
118                val = MERSENNE_LIST;
119            } else {
120                val = new ArrayList<java.math.BigInteger>(50);
121                addMersenne();
122                MERSENNE_LIST = val;
123            }
124            break;
125        }
126        last = get(size() - 1);
127    }
128
129
130    /**
131     * Add small primes.
132     */
133    private void addSmall() {
134        // really small
135        val.add(java.math.BigInteger.valueOf(2L));
136        val.add(java.math.BigInteger.valueOf(3L));
137        val.add(java.math.BigInteger.valueOf(5L));
138        val.add(java.math.BigInteger.valueOf(7L));
139        val.add(java.math.BigInteger.valueOf(11L));
140        val.add(java.math.BigInteger.valueOf(13L));
141        val.add(java.math.BigInteger.valueOf(17L));
142        val.add(java.math.BigInteger.valueOf(19L));
143        val.add(java.math.BigInteger.valueOf(23L));
144        val.add(java.math.BigInteger.valueOf(29L));
145    }
146
147
148    /**
149     * Add low sized primes.
150     */
151    private void addLow() {
152        // 2^15-x
153        val.add(getLongPrime(15, 19));
154        val.add(getLongPrime(15, 49));
155        val.add(getLongPrime(15, 51));
156        val.add(getLongPrime(15, 55));
157        val.add(getLongPrime(15, 61));
158        val.add(getLongPrime(15, 75));
159        val.add(getLongPrime(15, 81));
160        val.add(getLongPrime(15, 115));
161        val.add(getLongPrime(15, 121));
162        val.add(getLongPrime(15, 135));
163        // 2^16-x
164        val.add(getLongPrime(16, 15));
165        val.add(getLongPrime(16, 17));
166        val.add(getLongPrime(16, 39));
167        val.add(getLongPrime(16, 57));
168        val.add(getLongPrime(16, 87));
169        val.add(getLongPrime(16, 89));
170        val.add(getLongPrime(16, 99));
171        val.add(getLongPrime(16, 113));
172        val.add(getLongPrime(16, 117));
173        val.add(getLongPrime(16, 123));
174    }
175
176
177    /**
178     * Add medium sized primes.
179     */
180    private void addMedium() {
181        // 2^28-x
182        val.add(getLongPrime(28, 57));
183        val.add(getLongPrime(28, 89));
184        val.add(getLongPrime(28, 95));
185        val.add(getLongPrime(28, 119));
186        val.add(getLongPrime(28, 125));
187        val.add(getLongPrime(28, 143));
188        val.add(getLongPrime(28, 165));
189        val.add(getLongPrime(28, 183));
190        val.add(getLongPrime(28, 213));
191        val.add(getLongPrime(28, 273));
192        // 2^29-x
193        val.add(getLongPrime(29, 3));
194        val.add(getLongPrime(29, 33));
195        val.add(getLongPrime(29, 43));
196        val.add(getLongPrime(29, 63));
197        val.add(getLongPrime(29, 73));
198        val.add(getLongPrime(29, 75));
199        val.add(getLongPrime(29, 93));
200        val.add(getLongPrime(29, 99));
201        val.add(getLongPrime(29, 121));
202        val.add(getLongPrime(29, 133));
203        // 2^32-x
204        val.add(getLongPrime(32, 5));
205        val.add(getLongPrime(32, 17));
206        val.add(getLongPrime(32, 65));
207        val.add(getLongPrime(32, 99));
208        val.add(getLongPrime(32, 107));
209        val.add(getLongPrime(32, 135));
210        val.add(getLongPrime(32, 153));
211        val.add(getLongPrime(32, 185));
212        val.add(getLongPrime(32, 209));
213        val.add(getLongPrime(32, 267));
214    }
215
216
217    /**
218     * Add large sized primes.
219     */
220    private void addLarge() {
221        // 2^59-x
222        val.add(getLongPrime(59, 55));
223        val.add(getLongPrime(59, 99));
224        val.add(getLongPrime(59, 225));
225        val.add(getLongPrime(59, 427));
226        val.add(getLongPrime(59, 517));
227        val.add(getLongPrime(59, 607));
228        val.add(getLongPrime(59, 649));
229        val.add(getLongPrime(59, 687));
230        val.add(getLongPrime(59, 861));
231        val.add(getLongPrime(59, 871));
232        // 2^60-x
233        val.add(getLongPrime(60, 93));
234        val.add(getLongPrime(60, 107));
235        val.add(getLongPrime(60, 173));
236        val.add(getLongPrime(60, 179));
237        val.add(getLongPrime(60, 257));
238        val.add(getLongPrime(60, 279));
239        val.add(getLongPrime(60, 369));
240        val.add(getLongPrime(60, 395));
241        val.add(getLongPrime(60, 399));
242        val.add(getLongPrime(60, 453));
243        // 2^63-x
244        val.add(getLongPrime(63, 25));
245        val.add(getLongPrime(63, 165));
246        val.add(getLongPrime(63, 259));
247        val.add(getLongPrime(63, 301));
248        val.add(getLongPrime(63, 375));
249        val.add(getLongPrime(63, 387));
250        val.add(getLongPrime(63, 391));
251        val.add(getLongPrime(63, 409));
252        val.add(getLongPrime(63, 457));
253        val.add(getLongPrime(63, 471));
254        // 2^64-x not possible
255    }
256
257
258    /**
259     * Add Mersenne sized primes.
260     */
261    private void addMersenne() {
262        // 2^n-1
263        val.add(getMersennePrime(2));
264        val.add(getMersennePrime(3));
265        val.add(getMersennePrime(5));
266        val.add(getMersennePrime(7));
267        val.add(getMersennePrime(13));
268        val.add(getMersennePrime(17));
269        val.add(getMersennePrime(19));
270        val.add(getMersennePrime(31));
271        val.add(getMersennePrime(61));
272        val.add(getMersennePrime(89));
273        val.add(getMersennePrime(107));
274        val.add(getMersennePrime(127));
275        val.add(getMersennePrime(521));
276        val.add(getMersennePrime(607));
277        val.add(getMersennePrime(1279));
278        val.add(getMersennePrime(2203));
279        val.add(getMersennePrime(2281));
280        val.add(getMersennePrime(3217));
281        val.add(getMersennePrime(4253));
282        val.add(getMersennePrime(4423));
283        val.add(getMersennePrime(9689));
284        val.add(getMersennePrime(9941));
285        val.add(getMersennePrime(11213));
286        val.add(getMersennePrime(19937));
287    }
288
289
290    /**
291     * Method to compute a prime as 2**n - m.
292     * @param n power for 2.
293     * @param m for 2**n - m.
294     * @return 2**n - m
295     */
296    public static java.math.BigInteger getLongPrime(int n, int m) {
297        if (n < 30) {
298            return java.math.BigInteger.valueOf((1 << n) - m);
299        }
300        return java.math.BigInteger.ONE.shiftLeft(n).subtract(java.math.BigInteger.valueOf(m));
301    }
302
303
304    /**
305     * Method to compute a Mersenne prime as 2**n - 1.
306     * @param n power for 2.
307     * @return 2**n - 1
308     */
309    public static java.math.BigInteger getMersennePrime(int n) {
310        return java.math.BigInteger.ONE.shiftLeft(n).subtract(java.math.BigInteger.ONE);
311    }
312
313
314    /**
315     * Check if the list contains really prime numbers.
316     */
317    protected boolean checkPrimes() {
318        return checkPrimes(size());
319    }
320
321
322    /**
323     * Check if the list contains really prime numbers.
324     */
325    protected boolean checkPrimes(int n) {
326        boolean isPrime;
327        int i = 0;
328        for (java.math.BigInteger p : val) {
329            if (i++ >= n) {
330                break;
331            }
332            isPrime = p.isProbablePrime(63);
333            if (!isPrime) {
334                System.out.println("not prime = " + p);
335                return false;
336            }
337        }
338        return true;
339    }
340
341
342    /**
343     * toString.
344     */
345    @Override
346    public String toString() {
347        return val.toString();
348    }
349
350
351    /**
352     * size of current list.
353     */
354    public int size() {
355        return val.size();
356    }
357
358
359    /**
360     * get prime at index i.
361     */
362    public java.math.BigInteger get(int i) {
363        java.math.BigInteger p;
364        if (i < size()) {
365            p = val.get(i);
366        } else if (i == size()) {
367            p = last.nextProbablePrime();
368            val.add(p);
369            last = p;
370        } else {
371            p = get(i-1);
372            p = last.nextProbablePrime();
373            val.add(p);
374            last = p;
375        }
376        return p;
377    }
378
379
380    /**
381     * Iterator.
382     */
383    public Iterator<java.math.BigInteger> iterator() {
384        return new Iterator<java.math.BigInteger>() {
385
386
387            int index = -1;
388
389
390            public boolean hasNext() {
391                return true;
392            }
393
394
395            public void remove() {
396                throw new UnsupportedOperationException("remove not implemented");
397            }
398
399
400            public java.math.BigInteger next() {
401                index++;
402                return get(index);
403            }
404        };
405    }
406
407}