View Single Post
Old 2007-05-24, 01:02   #23
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

Geoff, I think I misunderstood your post the last time I read it.

Here is what I think will be best. We will look at primes such that

p=2^y*t*x*m+1

1) Using a switch (y) you only sieve for values that are p==1 (mod 2^y). This is already implemented.

2) t=p-1%1440. We do SPH over the t value. It would be nice if this could be set as a switch so that the POWER_RESIDUE_DIVISORS, POWER_LCM etc can be modified, so memory needs can be tested out.
Btw, why do you have to look stuff up a table, can't you factorize the p-1%1440 over small integers?

Of these 1440 values we only need to look at a fraction of t's. *** (See below)

3) We do BSGS algorithm on the rest of x
4) m is the extra non-useful part of the prime.

*** So we decide on which t's we want to use based on work done. Work done~= sqrt(remaining number of the first 1440 with no small factors)

For example if p-1%1440=36, then
36=2^2*3^2. (We do SPH over this)
1440/36=60

So workdone for 36= sqrt(60)=~7.5

So if we could have a switch to choose primes that fall in a certain work done range. All this can be calculated at the start of the program. Here is the work done for all p-1%1440 that you would look at.


Code:
p-1%1440 workdone
6 15.4919
10 12
12 10.9545
16 9.48683
18 8.94427
22 26.8328
28 18.9737
30 6.9282
36 6.32456
40 6
42 15.4919
46 26.8328
48 5.47723
52 18.9737
58 26.8328
60 4.89898
66 15.4919
70 12
72 4.47214
76 18.9737
78 15.4919
82 26.8328
88 13.4164
90 4
96 3.87298
100 8.48528
102 15.4919
106 26.8328
108 6.32456
112 9.48683
118 26.8328
120 3.4641
126 8.94427
130 12
132 10.9545
136 13.4164
138 15.4919
142 26.8328
148 18.9737
150 6.9282
156 10.9545
160 3
162 8.94427
166 26.8328
168 7.74597
172 18.9737
178 26.8328
180 2.82843
186 15.4919
190 12
192 3.87298
196 18.9737
198 8.94427
202 26.8328
208 9.48683
210 6.9282
216 4.47214
220 8.48528
222 15.4919
226 26.8328
228 10.9545
232 13.4164
238 26.8328
240 2.44949
246 15.4919
250 12
252 6.32456
256 6.7082
258 15.4919
262 26.8328
268 18.9737
270 4
276 10.9545
280 6
282 15.4919
286 26.8328
288 2.23607
292 18.9737
298 26.8328
300 4.89898
306 8.94427
310 12
312 7.74597
316 18.9737
318 15.4919
322 26.8328
328 13.4164
330 6.9282
336 5.47723
340 8.48528
342 8.94427
346 26.8328
348 10.9545
352 6.7082
358 26.8328
360 2
366 15.4919
370 12
372 10.9545
376 13.4164
378 8.94427
382 26.8328
388 18.9737
390 6.9282
396 6.32456
400 4.24264
402 15.4919
406 26.8328
408 7.74597
412 18.9737
418 26.8328
420 4.89898
426 15.4919
430 12
432 3.16228
436 18.9737
438 15.4919
442 26.8328
448 6.7082
450 4
456 7.74597
460 8.48528
462 15.4919
466 26.8328
468 6.32456
472 13.4164
478 26.8328
480 1.73205
486 8.94427
490 12
492 10.9545
496 9.48683
498 15.4919
502 26.8328
508 18.9737
510 6.9282
516 10.9545
520 6
522 8.94427
526 26.8328
528 5.47723
532 18.9737
538 26.8328
540 2.82843
546 15.4919
550 12
552 7.74597
556 18.9737
558 8.94427
562 26.8328
568 13.4164
570 6.9282
576 2.23607
580 8.48528
582 15.4919
586 26.8328
588 10.9545
592 9.48683
598 26.8328
600 3.4641
606 15.4919
610 12
612 6.32456
616 13.4164
618 15.4919
622 26.8328
628 18.9737
630 4
636 10.9545
640 3
642 15.4919
646 26.8328
648 4.47214
652 18.9737
658 26.8328
660 4.89898
666 8.94427
670 12
672 3.87298
676 18.9737
678 15.4919
682 26.8328
688 9.48683
690 6.9282
696 7.74597
700 8.48528
702 8.94427
706 26.8328
708 10.9545
712 13.4164
718 26.8328
720 1.41421
726 15.4919
730 12
732 10.9545
736 6.7082
738 8.94427
742 26.8328
748 18.9737
750 6.9282
756 6.32456
760 6
762 15.4919
766 26.8328
768 3.87298
772 18.9737
778 26.8328
780 4.89898
786 15.4919
790 12
792 4.47214
796 18.9737
798 15.4919
802 26.8328
808 13.4164
810 4
816 5.47723
820 8.48528
822 15.4919
826 26.8328
828 6.32456
832 6.7082
838 26.8328
840 3.4641
846 8.94427
850 12
852 10.9545
856 13.4164
858 15.4919
862 26.8328
868 18.9737
870 6.9282
876 10.9545
880 4.24264
882 8.94427
886 26.8328
888 7.74597
892 18.9737
898 26.8328
900 2.82843
906 15.4919
910 12
912 5.47723
916 18.9737
918 8.94427
922 26.8328
928 6.7082
930 6.9282
936 4.47214
940 8.48528
942 15.4919
946 26.8328
948 10.9545
952 13.4164
958 26.8328
960 1.73205
966 15.4919
970 12
972 6.32456
976 9.48683
978 15.4919
982 26.8328
988 18.9737
990 4
996 10.9545
1000 6
1002 15.4919
1006 26.8328
1008 3.16228
1012 18.9737
1018 26.8328
1020 4.89898
1026 8.94427
1030 12
1032 7.74597
1036 18.9737
1038 15.4919
1042 26.8328
1048 13.4164
1050 6.9282
1056 3.87298
1060 8.48528
1062 8.94427
1066 26.8328
1068 10.9545
1072 9.48683
1078 26.8328
1080 2
1086 15.4919
1090 12
1092 10.9545
1096 13.4164
1098 8.94427
1102 26.8328
1108 18.9737
1110 6.9282
1116 6.32456
1120 3
1122 15.4919
1126 26.8328
1128 7.74597
1132 18.9737
1138 26.8328
1140 4.89898
1146 15.4919
1150 12
1152 2.23607
1156 18.9737
1158 15.4919
1162 26.8328
1168 9.48683
1170 4
1176 7.74597
1180 8.48528
1182 15.4919
1186 26.8328
1188 6.32456
1192 13.4164
1198 26.8328
1200 2.44949
1206 8.94427
1210 12
1212 10.9545
1216 6.7082
1218 15.4919
1222 26.8328
1228 18.9737
1230 6.9282
1236 10.9545
1240 6
1242 8.94427
1246 26.8328
1248 3.87298
1252 18.9737
1258 26.8328
1260 2.82843
1266 15.4919
1270 12
1272 7.74597
1276 18.9737
1278 8.94427
1282 26.8328
1288 13.4164
1290 6.9282
1296 3.16228
1300 8.48528
1302 15.4919
1306 26.8328
1308 10.9545
1312 6.7082
1318 26.8328
1320 3.4641
1326 15.4919
1330 12
1332 6.32456
1336 13.4164
1338 15.4919
1342 26.8328
1348 18.9737
1350 4
1356 10.9545
1360 4.24264
1362 15.4919
1366 26.8328
1368 4.47214
1372 18.9737
1378 26.8328
1380 4.89898
1386 8.94427
1390 12
1392 5.47723
1396 18.9737
1398 15.4919
1402 26.8328
1408 6.7082
1410 6.9282
1416 7.74597
1420 8.48528
1422 8.94427
1426 26.8328
1428 10.9545
1432 13.4164
1438 26.8328
1440 1

Let me know if you have any questions? Could you please implement this soon.
Thanks!
Citrix is offline   Reply With Quote