Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import java.util.List;
009import java.util.SortedMap;
010
011import junit.framework.Test;
012import junit.framework.TestCase;
013import junit.framework.TestSuite;
014
015
016/**
017 * PrimeInteger and PrimeList tests with JUnit.
018 * @author Heinz Kredel
019 */
020
021public class PrimeTest extends TestCase {
022
023
024    /**
025     * main.
026     */
027    public static void main(String[] args) {
028        junit.textui.TestRunner.run(suite());
029    }
030
031
032    /**
033     * Constructs a <CODE>PrimeTest</CODE> object.
034     * @param name String
035     */
036    public PrimeTest(String name) {
037        super(name);
038    }
039
040
041    /**
042     */
043    public static Test suite() {
044        TestSuite suite = new TestSuite(PrimeTest.class);
045        return suite;
046    }
047
048
049    @Override
050    protected void setUp() {
051    }
052
053
054    @Override
055    protected void tearDown() {
056    }
057
058
059    /**
060     * Test prime list.
061     */
062    public void testPrime() {
063        PrimeList primes = new PrimeList();
064        //System.out.println("primes = " + primes);
065        int i = 0;
066        //System.out.println("primes = ");
067        for (java.math.BigInteger p : primes) {
068            assertFalse("p != null", p == null);
069            //System.out.print("" + p);
070            if (i++ > 50) {
071                break;
072            }
073            //System.out.print(", ");
074        }
075        //System.out.println();
076        //System.out.println("primes = " + primes);
077        assertTrue("all primes ", primes.checkPrimes());
078    }
079
080
081    /**
082     * Test small prime list.
083     */
084    public void testSmallPrime() {
085        List<Long> sp = PrimeInteger.SMPRM; //smallPrimes(1, 500);
086        //System.out.println("sp = " + sp);
087        for (Long p : sp) {
088            java.math.BigInteger P = new java.math.BigInteger(p.toString());
089            assertTrue("isPrime: " + p, P.isProbablePrime(16));
090        }
091        PrimeList primes = new PrimeList(PrimeList.Range.small);
092        //System.out.println("primes = " + primes);
093        int i = primes.size() - 1;
094        //System.out.println("primes = ");
095        for (java.math.BigInteger p : primes) {
096            assertTrue("p.isPrime: ", PrimeInteger.isPrime(p.longValue()));
097            //System.out.print(i + " = " + p + ", ");
098            if (i-- <= 0) {
099                break;
100            }
101        }
102    }
103
104
105    /**
106     * Test low prime list.
107     */
108    public void testLowPrime() {
109        PrimeList primes = new PrimeList(PrimeList.Range.low);
110        //System.out.println("primes = " + primes);
111        int i = primes.size() - 1;
112        //System.out.println("primes = ");
113        for (java.math.BigInteger p : primes) {
114            assertTrue("p.isPrime: ", PrimeInteger.isPrime(p.longValue()));
115            //System.out.print(i + " = " + p + ", ");
116            if (i-- <= 0) {
117                break;
118            }
119        }
120    }
121
122
123    /**
124     * Test medium prime list.
125     */
126    public void testMediumPrime() {
127        PrimeList primes = new PrimeList(PrimeList.Range.medium);
128        //System.out.println("primes = " + primes);
129        int i = primes.size() - 1;
130        //System.out.println("primes = ");
131        for (java.math.BigInteger p : primes) {
132            //System.out.println(i + " = " + p + ", ");
133            assertTrue("p.isPrime: ", PrimeInteger.isPrime(p.longValue()));
134            if (i-- <= 0) {
135                break;
136            }
137        }
138    }
139
140
141    /**
142     * Test xlarge prime list.
143     */
144    public void testLargePrime() {
145        PrimeList primes = new PrimeList(PrimeList.Range.large);
146        //System.out.println("primes = " + primes);
147        int i = primes.size() - 1;
148        //System.out.println("primes = ");
149        for (java.math.BigInteger p : primes) {
150            //System.out.println(i + " = " + p + ", ");
151            long pl = p.longValue();
152            if (pl < PrimeInteger.BETA) {
153                assertTrue("p.isPrime: ", PrimeInteger.isPrime(pl));
154            } else {
155                break;
156            }
157            if (i-- <= 0) {
158                break;
159            }
160        }
161    }
162
163
164    /**
165     * Test Mersenne prime list.
166     */
167    public void testMersennePrime() {
168        PrimeList primes = new PrimeList(PrimeList.Range.mersenne);
169        //System.out.println("primes = " + primes);
170        //assertTrue("all primes ", primes.checkPrimes() );
171        int i = primes.size() - 1;
172        //System.out.println("primes = ");
173        for (java.math.BigInteger p : primes) {
174            //System.out.println(i + " = " + p + ", ");
175            long pl = p.longValue();
176            if (pl < PrimeInteger.BETA) {
177                assertTrue("p.isPrime: ", PrimeInteger.isPrime(pl));
178            } else {
179                break;
180            }
181            if (i-- <= 0) {
182                break;
183            }
184        }
185        assertTrue("all primes ", primes.checkPrimes(5));
186    }
187
188
189    /**
190     * Test factorize integer.
191     */
192    public void testFactorInteger() {
193        SortedMap<Long, Integer> ff;
194
195        ff = PrimeInteger.factors(2 * 3 * 5 * 7 * 2 * 9 * 10 * 19 * 811);
196        //System.out.println("ff = " + ff);
197        assertEquals("factors: ", ff.size(), 6);
198        for (Long p : ff.keySet()) {
199            java.math.BigInteger P = java.math.BigInteger.valueOf(p);
200            assertTrue("isPrime: " + p, P.isProbablePrime(16));
201        }
202
203        ff = PrimeInteger.factors(991 * 997 * 811 + 1);
204        //System.out.println("ff = " + ff);
205        assertEquals("factors: ", ff.size(), 3);
206        for (Long p : ff.keySet()) {
207            java.math.BigInteger P = java.math.BigInteger.valueOf(p);
208            assertTrue("isPrime: " + p, P.isProbablePrime(16));
209        }
210
211        ff = PrimeInteger.factors(PrimeList.getLongPrime(15, 135).longValue());
212        //System.out.println("ff = " + ff);
213        assertEquals("factors: ", ff.size(), 1);
214        for (Long p : ff.keySet()) {
215            java.math.BigInteger P = java.math.BigInteger.valueOf(p);
216            assertTrue("isPrime: " + p, P.isProbablePrime(16));
217        }
218
219        //ff = PrimeInteger.factors( PrimeList.getLongPrime(61, 1).longValue() );
220        //ff = PrimeInteger.factors( PrimeList.getLongPrime(60, 93).longValue() );
221        //ff = PrimeInteger.factors( PrimeList.getLongPrime(59, 55).longValue() );
222        ff = PrimeInteger.factors(PrimeList.getLongPrime(59, 0).longValue());
223        //System.out.println("m = " + PrimeList.getLongPrime(59, 0).longValue());
224        //System.out.println("ff = " + ff);
225        assertEquals("factors: ", ff.size(), 1);
226        for (Long p : ff.keySet()) {
227            java.math.BigInteger P = java.math.BigInteger.valueOf(p);
228            assertTrue("isPrime: " + p, P.isProbablePrime(32));
229        }
230        //System.out.println("SMPRM = " + PrimeInteger.SMPRM);
231    }
232
233
234    /**
235     * Test factorize large integer.
236     */
237    public void testFactorLargeInteger() {
238        SortedMap<java.math.BigInteger, Integer> ff;
239
240        long n = 2 * 3 * 5 * 7 * 2 * 9 * 10 * 19 * 811;
241        java.math.BigInteger N = java.math.BigInteger.valueOf(n);
242        ff = PrimeInteger.factors(N);
243        //System.out.println("ff = " + ff);
244        assertEquals("factors: ", ff.size(), 6);
245        for (java.math.BigInteger p : ff.keySet()) {
246            assertTrue("isPrime: " + p, p.isProbablePrime(16));
247        }
248
249        //N = N.multiply( PrimeList.getLongPrime(59, 55) );
250        N = N.multiply(PrimeList.getLongPrime(59, 19));
251        N = N.multiply(PrimeList.getLongPrime(61, 1));
252        //System.out.println("N = " + N);
253        ff = PrimeInteger.factors(N); // was not correct
254        //System.out.println("ff = " + ff);
255        for (java.math.BigInteger p : ff.keySet()) {
256            assertTrue("isPrime: " + p, p.isProbablePrime(32));
257        }
258
259        N = new java.math.BigInteger("1152921504606846883");
260        //System.out.println("N = " + N);
261        ff = PrimeInteger.factors(N);
262        //System.out.println("ff = " + ff);
263        assertTrue("isPrime: " + ff, ff.size() == 1);
264    }
265
266
267    /**
268     * Test random integers.
269     */
270    public void testRandom() {
271        SortedMap<Long, Integer> ff;
272        BigInteger rnd = BigInteger.ONE;
273        //System.out.println("beta = " + PrimeInteger.BETA);
274        //System.out.println("SMPRM = " + PrimeInteger.SMPRM);
275        for (int i = 0; i < 5; i++) {
276            BigInteger M = rnd.random(60).abs();
277            //System.out.println("M = " + M);
278            long m = Math.abs(M.getVal().longValue());
279            //System.out.println("M = " + M + ", m = " + m);
280            if (m < PrimeInteger.BETA) {
281                ff = PrimeInteger.factors(m);
282                //System.out.println("ff = " + ff);
283                assertTrue("isFactorization: " + m + ", ff = " + ff,
284                                PrimeInteger.isPrimeFactorization(m, ff));
285            }
286        }
287    }
288
289
290    /**
291     * Test random integers to the power of 3.
292     */
293    public void testRandom3() {
294        SortedMap<Long, Integer> ff;
295        BigInteger rnd = BigInteger.ONE;
296        for (int i = 0; i < 5; i++) {
297            BigInteger M = rnd.random(20).abs();
298            M = M.power(3);
299            //System.out.println("M = " + M);
300            long m = Math.abs(M.getVal().longValue());
301            //System.out.println("M = " + M + ", m = " + m);
302            if (m < PrimeInteger.BETA) {
303                ff = PrimeInteger.factors(m);
304                //System.out.println("ff = " + ff);
305                assertTrue("isFactorization: " + m + ", ff = " + ff,
306                                PrimeInteger.isPrimeFactorization(m, ff));
307                for (Integer e : ff.values()) {
308                    assertTrue("e >= 3: " + e + ", ff = " + ff, e >= 3);
309                }
310            }
311        }
312    }
313
314
315    /**
316     * Test random integers, compare to Pollard.
317     */
318    public void ytestRandomCompare() {
319        SortedMap<Long, Integer> ff, ffp;
320        BigInteger rnd = BigInteger.ONE;
321        //System.out.println("beta = " + PrimeInteger.BETA);
322
323        for (int i = 0; i < 5; i++) {
324            BigInteger M = rnd.random(60).abs();
325            //System.out.println("M = " + M);
326            long m = Math.abs(M.getVal().longValue());
327            //System.out.println("M = " + M + ", m = " + m);
328            if (m < PrimeInteger.BETA) {
329                long t = System.currentTimeMillis();
330                ff = PrimeInteger.factors(m);
331                t = System.currentTimeMillis() - t;
332                System.out.println("ff = " + ff);
333                assertTrue("isFactorization: " + m + ", ff = " + ff, PrimeInteger.isFactorization(m, ff));
334                long s = System.currentTimeMillis();
335                ffp = PrimeInteger.factorsPollard(m);
336                s = System.currentTimeMillis() - s;
337                System.out.println("time: t = " + t + ", s = " + s);
338                assertEquals("isFactorization: " + m, ff, ffp);
339            }
340        }
341
342        for (int i = 0; i < 5; i++) {
343            BigInteger M = rnd.random(20).abs();
344            M = M.power(3);
345            //System.out.println("M = " + M);
346            long m = Math.abs(M.getVal().longValue());
347            //System.out.println("M = " + M + ", m = " + m);
348            if (m < PrimeInteger.BETA) {
349                long t = System.currentTimeMillis();
350                ff = PrimeInteger.factors(m);
351                t = System.currentTimeMillis() - t;
352                System.out.println("ff = " + ff);
353                assertTrue("isFactorization: " + m + ", ff = " + ff, PrimeInteger.isFactorization(m, ff));
354                long s = System.currentTimeMillis();
355                ffp = PrimeInteger.factorsPollard(m);
356                s = System.currentTimeMillis() - s;
357                System.out.println("time: t = " + t + ", s = " + s);
358                assertEquals("isFactorization: " + m, ff, ffp);
359            }
360        }
361    }
362
363}