Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import java.util.ArrayList;
009import java.util.Iterator;
010import java.util.List;
011
012
013/**
014 * List of big primes. Provides an Iterator for generating prime numbers.
015 * Similar to ALDES/SAC2 SACPOL.PRIME list.
016 * See Knuth vol 2, page 390, for list of known primes. See also ALDES/SAC2
017 *      SACPOL.PRIME
018 * 
019 * @author Heinz Kredel
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     * @return true if all checked numbers are prime
317     */
318    protected boolean checkPrimes() {
319        return checkPrimes(size());
320    }
321
322
323    /**
324     * Check if the list contains really prime numbers.
325     * @param n number of primes to check.
326     * @return true if all checked numbers are prime
327     */
328    protected boolean checkPrimes(int n) {
329        boolean isPrime;
330        int i = 0;
331        for (java.math.BigInteger p : val) {
332            if (i++ >= n) {
333                break;
334            }
335            isPrime = p.isProbablePrime(63);
336            if (!isPrime) {
337                System.out.println("not prime = " + p);
338                return false;
339            }
340        }
341        return true;
342    }
343
344
345    /**
346     * {@inheritDoc}
347     */
348    @Override
349    public String toString() {
350        return val.toString();
351    }
352
353
354    /**
355     * Size of current list.
356     * @return current size of list.
357     */
358    public int size() {
359        return val.size();
360    }
361
362
363    /**
364     * Get prime at index i.
365     * @param i index to get element.
366     * @return prime at index i.
367     */
368    public java.math.BigInteger get(int i) {
369        java.math.BigInteger p;
370        if (i < size()) {
371            p = val.get(i);
372        } else if (i == size()) {
373            p = last.nextProbablePrime();
374            val.add(p);
375            last = p;
376        } else {
377            p = get(i - 1);
378            p = last.nextProbablePrime();
379            val.add(p);
380            last = p;
381        }
382        return p;
383    }
384
385
386    /**
387     * Iterator. 
388     * Always has next, will generate new primes if required.
389     * @return iterator over the prime list.
390     */
391    public Iterator<java.math.BigInteger> iterator() {
392        return new Iterator<java.math.BigInteger>() {
393
394
395            int index = -1;
396
397
398            public boolean hasNext() {
399                return true;
400            }
401
402
403            public void remove() {
404                throw new UnsupportedOperationException("remove not implemented");
405            }
406
407
408            public java.math.BigInteger next() {
409                index++;
410                return get(index);
411            }
412        };
413    }
414
415}