Source code

001/*
002 * $Id: PrimeTest.java 5688 2017-01-03 08:45:09Z kredel $
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
260
261    /**
262     * Test random integers.
263     */
264    public void testRandom() {
265        SortedMap<Long, Integer> ff;
266        BigInteger rnd = BigInteger.ONE;
267        //System.out.println("beta = " + PrimeInteger.BETA);
268        //System.out.println("SMPRM = " + PrimeInteger.SMPRM);
269        for (int i = 0; i < 5; i++) {
270            BigInteger M = rnd.random(60).abs();
271            //System.out.println("M = " + M);
272            long m = Math.abs(M.getVal().longValue());
273            //System.out.println("M = " + M + ", m = " + m);
274            if (m < PrimeInteger.BETA) {
275                ff = PrimeInteger.factors(m);
276                //System.out.println("ff = " + ff);
277                assertTrue("isFactorization: " + m + ", ff = " + ff,
278                                PrimeInteger.isPrimeFactorization(m, ff));
279            }
280        }
281    }
282
283
284    /**
285     * Test random integers to the power of 3.
286     */
287    public void testRandom3() {
288        SortedMap<Long, Integer> ff;
289        BigInteger rnd = BigInteger.ONE;
290        for (int i = 0; i < 5; i++) {
291            BigInteger M = rnd.random(20).abs();
292            M = M.power(3);
293            //System.out.println("M = " + M);
294            long m = Math.abs(M.getVal().longValue());
295            //System.out.println("M = " + M + ", m = " + m);
296            if (m < PrimeInteger.BETA) {
297                ff = PrimeInteger.factors(m);
298                //System.out.println("ff = " + ff);
299                assertTrue("isFactorization: " + m + ", ff = " + ff,
300                                PrimeInteger.isPrimeFactorization(m, ff));
301                for (Integer e : ff.values()) {
302                    assertTrue("e >= 3: " + e + ", ff = " + ff, e >= 3);
303                }
304            }
305        }
306    }
307
308
309    /**
310     * Test random integers, compare to Pollard.
311     */
312    public void ytestRandomCompare() {
313        SortedMap<Long, Integer> ff, ffp;
314        BigInteger rnd = BigInteger.ONE;
315        //System.out.println("beta = " + PrimeInteger.BETA);
316
317        for (int i = 0; i < 5; i++) {
318            BigInteger M = rnd.random(60).abs();
319            //System.out.println("M = " + M);
320            long m = Math.abs(M.getVal().longValue());
321            //System.out.println("M = " + M + ", m = " + m);
322            if (m < PrimeInteger.BETA) {
323                long t = System.currentTimeMillis();
324                ff = PrimeInteger.factors(m);
325                t = System.currentTimeMillis() - t;
326                System.out.println("ff = " + ff);
327                assertTrue("isFactorization: " + m + ", ff = " + ff, PrimeInteger.isFactorization(m, ff));
328                long s = System.currentTimeMillis();
329                ffp = PrimeInteger.factorsPollard(m);
330                s = System.currentTimeMillis() - s;
331                System.out.println("time: t = " + t + ", s = " + s);
332                assertEquals("isFactorization: " + m, ff, ffp);
333            }
334        }
335
336        for (int i = 0; i < 5; i++) {
337            BigInteger M = rnd.random(20).abs();
338            M = M.power(3);
339            //System.out.println("M = " + M);
340            long m = Math.abs(M.getVal().longValue());
341            //System.out.println("M = " + M + ", m = " + m);
342            if (m < PrimeInteger.BETA) {
343                long t = System.currentTimeMillis();
344                ff = PrimeInteger.factors(m);
345                t = System.currentTimeMillis() - t;
346                System.out.println("ff = " + ff);
347                assertTrue("isFactorization: " + m + ", ff = " + ff, PrimeInteger.isFactorization(m, ff));
348                long s = System.currentTimeMillis();
349                ffp = PrimeInteger.factorsPollard(m);
350                s = System.currentTimeMillis() - s;
351                System.out.println("time: t = " + t + ", s = " + s);
352                assertEquals("isFactorization: " + m, ff, ffp);
353            }
354        }
355    }
356
357}