tests/rtestifactor.mac

   1 /* kill(all); */
   2 /* done; */
   3
   4 /* PRIMALITY TESTS */
   5
   6 /* 0 and 1 are not primes */
   7 primep(0);
   8 false;
   9
  10 primep(1);
  11 false;
  12
  13 primep(2);
  14 true;
  15
  16 primep(6);
  17 false;
  18
  19 /* this is checked from the list of small primes */
  20 primep(1741);
  21 true;
  22
  23 primep(8989);
  24 false;
  25
  26 /* this is the deterministic primality test */
  27 primep(1738727);
  28 true;
  29
  30 primep(5178997768267);
  31 false;
  32
  33 next_prime(100002100000);
  34 100002100043;
  35
  36 prev_prime(100002100042);
  37 100002099971;
  38
  39 /* Bug reported on mailing list by Walter Faxon on October 25th, 2017: "Bug in Maxima function primes()" */
  40 [primes(10005, 10009), primes(10006, 10009), primes(10007, 10009), primes(10008, 10009), primes(10009, 10009), primes(10010, 10010), primes(9972, 10007), primes(9973, 10007), primes(1, 2), primes(2, 2), primes(2, 3)];
  41 [[10007, 10009], [10007, 10009], [10007, 10009], [10009], [10009], [], [9973, 10007], [9973, 10007], [2], [2], [2, 3]]$
  42
  43 /* FACTORING TESTS */
  44
  45 ifactors(1);
  46 [];
  47
  48 /* trial divisions */
  49 ifactors(226800);
  50 [[2,4],[3,4],[5,2],[7,1]];
  51
  52 /* limiting to factors */
  53 ev( ifactors(226800), factors_only:true );
  54 [2,3,5,7];
  55
  56 /* this is still found by trialdivision */
  57 ifactors(5178997768267);
  58 [[183823,1],[28173829,1]];
  59
  60 /* disable Pollard p-1 to test Pollard rho */
  61 (save_pm1 : pollard_pm1_tests, pollard_pm1_tests : 0);
  62 0;
  63
  64 /* this should be found by Pollard rho */
  65 ifactors(25091429338142886343);
  66 [[3873703993, 1], [6477373951, 1]];
  67
  68 (pollard_pm1_tests : save_pm1, 0);
  69 0;
  70
  71 (save_prt : pollard_rho_tests, pollard_rho_tests : 0);
  72 0;
  73
  74 /* now this should be found by Pollard p-1 */
  75 ifactors(25091429338142886343);
  76 [[3873703993, 1], [6477373951, 1]];
  77
  78 (pollard_rho_tests : save_prt, 0);
  79 0;
  80
  81 /* disable Pollard rho and p-1 to test ECM */
  82 (save_prt : pollard_rho_tests, pollard_rho_tests : 0);
  83 0;
  84
  85 (save_pm1 : pollard_pm1_tests, pollard_pm1_tests : 0);
  86 0;
  87
  88 /* now this should be found by ECM */
  89 ifactors(25091429338142886343);
  90 [[3873703993, 1], [6477373951, 1]];
  91
  92 (pollard_rho_tests : save_prt, 0);
  93 0;
  94
  95 (pollard_pm1_tests : save_pm1, 0);
  96 0;
  97
  98 /* MODULAR POWERS AND INVERSE */
  99
 100 power_mod(2^64,2,2^64-2^34+1);
 101 240518168561;
 102
 103 inv_mod(42,2^64-2^34+1);
 104 18007535864707547137;
 105
 106 /* negative exponents */
 107 power_mod(3,-1,41);
 108 14;
 109
 110 inv_mod(3,41);
 111 14;
 112
 113 power_mod(2^64,-2,2^64-2^34+1);
 114 18446743816011514066;
 115
 116 inv_mod(2^128,2^64-2^34+1);
 117 18446743816011514066;
 118
 119 /* zero divisors */
 120 inv_mod(3,42);
 121 false;
 122
 123 power_mod(3,-1,42);
 124 false;