Source code

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