| blob | 90686b4116fc4a6ff3c17a4adc8cdb64d8762dda |
1 /*
2 * lucas_tbl - lucasian criteria for primality tables
3 *
4 * Copyright (C) 1999 Landon Curt Noll
5 *
6 * Calc is open software; you can redistribute it and/or modify it under
7 * the terms of the version 2.1 of the GNU Lesser General Public License
8 * as published by the Free Software Foundation.
9 *
10 * Calc is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
13 * Public License for more details.
14 *
15 * A copy of version 2.1 of the GNU Lesser General Public License is
16 * distributed with calc under the filename COPYING-LGPL. You should have
17 * received a copy with calc; if not, write to Free Software Foundation, Inc.
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 *
20 * @(#) $Revision: 30.1 $
21 * @(#) $Id: lucas_tbl.cal,v 30.1 2007/03/16 11:09:54 chongo Exp $
22 * @(#) $Source: /usr/local/src/bin/calc/cal/RCS/lucas_tbl.cal,v $
23 *
24 * Under source code control: 1991/01/26 02:43:43
25 * File existed as early as: 1991
26 *
27 * chongo <was here> /\oo/\ http://www.isthe.com/chongo/
28 * Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/
29 */
31 /*
32 * Lucasian criteria for primality
33 *
34 * The following table is taken from:
35 *
36 * "Lucasian Criteria for the Primality of N=h*2^n-1", by Hans Riesel,
37 * Mathematics of Computation, Vol 23 #108, p 872.
38 *
39 * The index of the *_val[] arrays correspond to the v(1) values found
40 * in the table. That is, for v(1) == x:
41 *
42 * D == d_val[x]
43 * a == a_val[x]
44 * b == b_val[x]
45 * r == r_val[x] (r == abs(a^2 - b^2*D))
46 *
47 *
48 * Note that when *_val[i] is not a number, the related v(1) value
49 * is not found in Table 1.
50 */
53 trymax = 100;
54 mat d_val[trymax+1];
55 mat a_val[trymax+1];
56 mat b_val[trymax+1];
57 mat r_val[trymax+1];
58 /* v1= 0 INVALID */
59 /* v1= 1 INVALID */
60 /* v1= 2 INVALID */
61 d_val[ 3]= 5; a_val[ 3]= 1; b_val[ 3]=1; r_val[ 3]=4;
62 d_val[ 4]= 3; a_val[ 4]= 1; b_val[ 4]=1; r_val[ 4]=2;
63 d_val[ 5]= 21; a_val[ 5]= 3; b_val[ 5]=1; r_val[ 5]=12;
64 d_val[ 6]= 2; a_val[ 6]= 1; b_val[ 6]=1; r_val[ 6]=1;
65 /* v1= 7 INVALID */
66 d_val[ 8]= 15; a_val[ 8]= 3; b_val[ 8]=1; r_val[ 8]=6;
67 d_val[ 9]= 77; a_val[ 9]= 7; b_val[ 9]=1; r_val[ 9]=28;
68 d_val[10]= 6; a_val[10]= 2; b_val[10]=1; r_val[10]=2;
69 d_val[11]= 13; a_val[11]= 3; b_val[11]=1; r_val[11]=4;
70 d_val[12]= 35; a_val[12]= 5; b_val[12]=1; r_val[12]=10;
71 d_val[13]= 165; a_val[13]=11; b_val[13]=1; r_val[13]=44;
72 /* v1=14 INVALID */
73 d_val[15]= 221; a_val[15]=13; b_val[15]=1; r_val[15]=52;
74 d_val[16]= 7; a_val[16]= 3; b_val[16]=1; r_val[16]=2;
75 d_val[17]= 285; a_val[17]=15; b_val[17]=1; r_val[17]=60;
76 /* v1=18 INVALID */
77 d_val[19]= 357; a_val[19]=17; b_val[19]=1; r_val[19]=68;
78 d_val[20]= 11; a_val[20]= 3; b_val[20]=1; r_val[20]=2;
79 d_val[21]= 437; a_val[21]=19; b_val[21]=1; r_val[21]=76;
80 d_val[22]= 30; a_val[22]= 5; b_val[22]=1; r_val[22]=5;
81 /* v1=23 INVALID */
82 d_val[24]= 143; a_val[24]=11; b_val[24]=1; r_val[24]=22;
83 d_val[25]= 69; a_val[25]= 9; b_val[25]=1; r_val[25]=12;
84 d_val[26]= 42; a_val[26]= 6; b_val[26]=1; r_val[26]=6;
85 d_val[27]= 29; a_val[27]= 5; b_val[27]=1; r_val[27]=4;
86 d_val[28]= 195; a_val[28]=13; b_val[28]=1; r_val[28]=26;
87 d_val[29]= 93; a_val[29]= 9; b_val[29]=1; r_val[29]=12;
88 d_val[30]= 14; a_val[30]= 4; b_val[30]=1; r_val[30]=2;
89 d_val[31]= 957; a_val[31]=29; b_val[31]=1; r_val[31]=116;
90 d_val[32]= 255; a_val[32]=15; b_val[32]=1; r_val[32]=30;
91 d_val[33]=1085; a_val[33]=31; b_val[33]=1; r_val[33]=124;
92 /* v1=34 INVALID */
93 d_val[35]=1221; a_val[35]=33; b_val[35]=1; r_val[35]=132;
94 d_val[36]= 323; a_val[36]=17; b_val[36]=1; r_val[36]=34;
95 d_val[37]=1365; a_val[37]=35; b_val[37]=1; r_val[37]=140;
96 d_val[38]= 10; a_val[38]= 3; b_val[38]=1; r_val[38]=1;
97 d_val[39]=1517; a_val[39]=37; b_val[39]=1; r_val[39]=148;
98 d_val[40]= 399; a_val[40]=19; b_val[40]=1; r_val[40]=38;
99 d_val[41]=1677; a_val[41]=39; b_val[41]=1; r_val[41]=156;
100 d_val[42]= 110; a_val[42]=10; b_val[42]=1; r_val[42]=10;
101 d_val[43]= 205; a_val[43]=15; b_val[43]=1; r_val[43]=20;
102 d_val[44]= 483; a_val[44]=21; b_val[44]=1; r_val[44]=42;
103 d_val[45]=2021; a_val[45]=43; b_val[45]=1; r_val[45]=172;
104 d_val[46]= 33; a_val[46]= 6; b_val[46]=1; r_val[46]=3;
105 /* v1=47 INVALID */
106 d_val[48]= 23; a_val[48]= 5; b_val[48]=1; r_val[48]=2;
107 d_val[49]=2397; a_val[49]=47; b_val[49]=1; r_val[49]=188;
108 d_val[50]= 39; a_val[50]= 6; b_val[50]=1; r_val[50]=3;
109 d_val[51]= 53; a_val[51]= 7; b_val[51]=1; r_val[51]=4;
110 /* v1=52 INVALID */
111 d_val[53]=2805; a_val[53]=51; b_val[53]=1; r_val[53]=204;
112 d_val[54]= 182; a_val[54]=13; b_val[54]=1; r_val[54]=13;
113 d_val[55]=3021; a_val[55]=53; b_val[55]=1; r_val[55]=212;
114 d_val[56]= 87; a_val[56]= 9; b_val[56]=1; r_val[56]=6;
115 d_val[57]=3245; a_val[57]=55; b_val[57]=1; r_val[57]=220;
116 d_val[58]= 210; a_val[58]=14; b_val[58]=1; r_val[58]=14;
117 d_val[59]=3477; a_val[59]=57; b_val[59]=1; r_val[59]=228;
118 d_val[60]= 899; a_val[60]=29; b_val[60]=1; r_val[60]=58;
119 d_val[61]= 413; a_val[61]=21; b_val[61]=1; r_val[61]=28;
120 /* v1=62 INVALID */
121 d_val[63]=3965; a_val[63]=61; b_val[63]=1; r_val[63]=244;
122 d_val[64]=1023; a_val[64]=31; b_val[64]=1; r_val[64]=62;
123 d_val[65]= 469; a_val[65]=21; b_val[65]=1; r_val[65]=28;
124 d_val[66]= 17; a_val[66]= 4; b_val[66]=1; r_val[66]=1;
125 d_val[67]=4485; a_val[67]=65; b_val[67]=1; r_val[67]=260;
126 d_val[68]=1155; a_val[68]=33; b_val[68]=1; r_val[68]=66;
127 d_val[69]=4757; a_val[69]=67; b_val[69]=1; r_val[69]=268;
128 d_val[70]= 34; a_val[70]= 6; b_val[70]=1; r_val[70]=2;
129 d_val[71]=5037; a_val[71]=69; b_val[71]=1; r_val[71]=276;
130 d_val[72]=1295; a_val[72]=35; b_val[72]=1; r_val[72]=70;
131 d_val[73]= 213; a_val[73]=15; b_val[73]=1; r_val[73]=12;
132 d_val[74]= 38; a_val[74]= 6; b_val[74]=1; r_val[74]=2;
133 d_val[75]=5621; a_val[75]=73; b_val[75]=1; r_val[75]=292;
134 d_val[76]=1443; a_val[76]=37; b_val[76]=1; r_val[76]=74;
135 d_val[77]= 237; a_val[77]=15; b_val[77]=1; r_val[77]=12;
136 d_val[78]= 95; a_val[78]=10; b_val[78]=1; r_val[78]=5;
137 /* v1=79 INVALID */
138 d_val[80]=1599; a_val[80]=39; b_val[80]=1; r_val[80]=78;
139 d_val[81]=6557; a_val[81]=79; b_val[81]=1; r_val[81]=316;
140 d_val[82]= 105; a_val[82]=10; b_val[82]=1; r_val[82]=5;
141 d_val[83]= 85; a_val[83]= 9; b_val[83]=1; r_val[83]=4;
142 d_val[84]=1763; a_val[84]=41; b_val[84]=1; r_val[84]=82;
143 d_val[85]=7221; a_val[85]=83; b_val[85]=1; r_val[85]=332;
144 d_val[86]= 462; a_val[86]=21; b_val[86]=1; r_val[86]=21;
145 d_val[87]=7565; a_val[87]=85; b_val[87]=1; r_val[87]=340;
146 d_val[88]= 215; a_val[88]=15; b_val[88]=1; r_val[88]=10;
147 d_val[89]=7917; a_val[89]=87; b_val[89]=1; r_val[89]=348;
148 d_val[90]= 506; a_val[90]=22; b_val[90]=1; r_val[90]=22;
149 d_val[91]=8277; a_val[91]=89; b_val[91]=1; r_val[91]=356;
150 d_val[92]= 235; a_val[92]=15; b_val[92]=1; r_val[92]=10;
151 d_val[93]=8645; a_val[93]=91; b_val[93]=1; r_val[93]=364;
152 d_val[94]= 138; a_val[94]=12; b_val[94]=1; r_val[94]=6;
153 d_val[95]=9021; a_val[95]=93; b_val[95]=1; r_val[95]=372;
154 d_val[96]= 47; a_val[96]= 7; b_val[96]=1; r_val[96]=2;
155 d_val[97]=1045; a_val[97]=33; b_val[97]=1; r_val[97]=44;
156 /* v1=98 INVALID */
157 d_val[99]=9797; a_val[99]=97; b_val[99]=1; r_val[99]=388;
158 d_val[100]= 51; a_val[100]= 7; b_val[100]=1; r_val[100]=2;
160 if (config("resource_debug") & 3) {
161 print "d_val[100] defined";
162 print "a_val[100] defined";
163 print "b_val[100] defined";
164 print "r_val[100] defined";
165 }