View Single Post
Old 2003-09-06, 11:38   #1
gbvalor
 
gbvalor's Avatar
 
Aug 2002

11011112 Posts
Default Primes for a mersenne integer DWT FNT

This last week I left an Athlon XP searching primes in the form
[code:1]
p = k * 2^q + 1
[/code:1]
to be used in a FNT transform. For an integer DWT to be used in a modular Mersenne arithmetic we also need the existence of proper roots of two. I wrote a GMP based code to search systematicaly these primes. Is not too much optimized but is not slow ( about 800000 trials per second in my Athlon XP 2500+). You can download at

ftp://ftp.oxixares.com/pub/glucas/ilucas-0.1.tar.gz

After configure and make, you can read a brief help

./psearch -h

I've only tested psearch in X86 targets.

I made a long run searching all primes having at least 2^24 th root of two for numbers from 25 to 62 bits. The list is long. What follows is the better ones (with roots of two and unity at least of 2^26). The format is, for a s*2^r valid root:
p (hexadecimal), p(decimal), s, r, small root of unity of order p-1, a root of unity of order s*2^r, a root of two of order s*2^r, and the factorization of p-1.

[code:1]
0x000ff04e78000001, 4486344462041089, 1, 26, 11, 2956743534207098, 2534241762335360, (7193*1549*3*2^27)
0x01dda25a30000001, 134442072127045633, 1, 28, 5, 14202908006974440, 38416365583369715, (5323*397*79*3*2^28)
0x02dbd19908000001, 205988663169908737, 1, 26, 5, 205669437681594801, 134613325924526488, (41467*73*13^2*3*2^27)
0x040e0cc4c8000001, 292185065134227457, 1, 26, 19, 158881768599504245, 44348138445373279, (241883153*3^2*2^27)
0x07e6d93540000001, 569381225639182337, 1, 28, 3, 146665363182891925, 373737386647402321, (530277589*2^30)
0x07fffaece4000001, 576455172671143937, 1, 26, 3, 339740298459922762, 106826103507306054, (300439*28591*2^26)
0x089f279ef8000001, 621258837319483393, 3, 26, 23, 247430348120354218, 461368420807572000, (3129641*29*17*3*2^27)
0x099649b6e8000001, 690820642773139457, 1, 27, 3, 334361055820297156, 646845165018050406, (302765581*17*2^27)
0x09f6e9ff34000001, 718018472910520321, 49, 26, 31, 327752487228664797, 464703741142552395, (8429*157*11*7^2*5*3*2^26)
0x0ac9ad8038000001, 777343176905064449, 1, 27, 3, 630431347559292957, 208289648825889548, (4409*199*41*23*7*2^27)
0x0b1052f75c000001, 797228356398481409, 1, 26, 3, 392632981377933164, 483000991053494976, (1422199*8353*2^26)
0x0c201b53e4000001, 873728374831316993, 1, 26, 3, 361688085632418079, 645118062240714450, (34429*1531*19*13*2^26)
0x0cd5994428000001, 924813816502419457, 3, 26, 7, 554684369476632643, 238614840738348519, (2296799959*3*2^27)
0x0d8df8f49c000001, 976710423682220033, 1, 26, 5, 278474532125113655, 111509898764842557, (5682983*197*13*2^26)
0x0dc75649c4000001, 992857117679419393, 1, 26, 13, 113145346672272579, 503552499055848415, (182650913*3^4*2^26)
0x0de7ac3278000001, 1001958774874832897, 1, 26, 3, 746619134835021329, 157588362536481380, (198031*149*23*11*2^27)
0x0e3622a4a4000001, 1024044055794810881, 1, 26, 3, 488269427790767265, 152470912434199161, (50030969*61*5*2^26)
0x0f3c18d6a4000001, 1097779719325089793, 1, 26, 19, 264312382562420289, 438304236734466310, (2228333*2447*3*2^26)
0x111ddc590c000001, 1233384147980910593, 1, 26, 3, 377843144979909225, 447045291288505038, (62726471*293*2^26)
0x12a5b7d1c8000001, 1343682175471452161, 1, 27, 3, 334429903422378648, 81492114934364874, (2002242469*5*2^27)
0x13669ae0cc000001, 1397975024631021569, 1, 26, 3, 1157281415442149401, 788870162067539560, (31231561*29*23*2^26)
0x14acf50dfc000001, 1489835017164029953, 3, 26, 17, 576403982379777951, 1217496306594615948, (569237737*13*3*2^26)
0x14c7a26f1c000001, 1497343999218810881, 1, 26, 3, 826087831612280885, 3699770312001190, (40939751*109*5*2^26)
0x1533ee1c5c000001, 1527826504178728961, 5, 26, 3, 961536035178335096, 918872096539104929, (4553277803*5*2^26)
0x15508b7d38000001, 1535880842860036097, 1, 26, 3, 1037146288658234910, 981618541284570884, (2437*1873*109*23*2^27)
0x16110c4a58000001, 1590065656882003969, 1, 27, 7, 795498821589657901, 563849041443623430, (3948970777*3*2^27)
0x169e44eccc000001, 1629815898980220929, 1, 26, 3, 1293620391333236633, 738488026520989437, (307419613*79*2^26)
0x173355a7d4000001, 1671774065989255169, 1, 26, 3, 253500402584444749, 125899044871034282, (673280401*37*2^26)
0x17eafac418000001, 1723465527545823233, 1, 27, 3, 1216173920984816684, 975283400163867802, (15602453*823*2^27)
0x185ec3c8f0000001, 1756056172508479489, 3, 27, 11, 1066150737387558173, 328123169860203926, (13057523*167*3*2^28)
0x18e546661c000001, 1793917430947381249, 9, 26, 19, 1199447079096636291, 280060442015752002, (2970161423*3^2*2^26)
0x196c4bc084000001, 1831922438653345793, 1, 26, 3, 491432681299295688, 222744005175096612, (4733*911*487*13*2^26)
0x1978a65fc8000001, 1835399778461024257, 1, 26, 7, 543492426188099148, 1652527452479821756, (12986509*13*3^4*2^27)
0x1bc631e684000001, 2001341950539595777, 7, 26, 43, 1892824508735447530, 135416102482748349, (156797*3019*7*3^2*2^26)
0x1cb3ec2228000001, 2068256285337321473, 1, 27, 3, 381679717147806527, 592009946307101677, (375846589*41*2^27)
0x1f3c2e2bb4000001, 2250724679016775681, 1, 26, 23, 1120209764861288188, 211656614197246419, (321203*6961*5*3*2^26)
0x1f832d661c000001, 2270708553704538113, 1, 26, 5, 1362403533105130967, 2001390660479887798, (3564331*863*11*2^26)
0x21499e999c000001, 2398622659135930369, 9, 26, 23, 861431578568445555, 576311146788870038, (8964701*443*3^2*2^26)
0x227e1d06e4000001, 2485455959787307009, 3, 26, 7, 681888733638616278, 1522226130946868853, (12345393299*3*2^26)
0x23881e62d4000001, 2560329797972525057, 1, 26, 3, 1421751396220275612, 2426702380623961098, (38151887029*2^26)
0x23c33e1230000001, 2576971659621695489, 1, 26, 3, 47991005390020579, 2567531320003683670, (45013*509*419*2^28)
0x23d54cecc4000001, 2582054541151174657, 1, 26, 5, 335167499971725653, 105217944468263621, (472331*431*7*3^3*2^26)
0x24e3241724000001, 2658007886885552129, 1, 26, 3, 17087961293468997, 2502952362987393078, (747309509*53*2^26)
0x250655a3ac000001, 2667913990717308929, 7, 26, 3, 1408772344356920451, 1708937673388724268, (228203*607*41*7*2^26)
0x2543e417f0000001, 2685240594304860161, 1, 28, 7, 437521231975298786, 2246643140016868175, (418811*281*17*5*2^28)
0x263381a61c000001, 2752686347687821313, 1, 26, 3, 1211497281217223080, 582120517783096743, (1000444463*41*2^26)
0x270b8fcc50000001, 2813500499901284353, 1, 26, 5, 1493683036924742258, 1803913865741770605, (2349497*1487*3*2^28)
0x27d65c0dcc000001, 2870583026822152193, 1, 26, 3, 1544040082115877118, 1267223265068524320, (1799311*23773*2^26)
0x28c6855830000001, 2938182420714749953, 1, 26, 5, 1443447788221454795, 2203004921239146984, (3648527489*3*2^28)
0x29372c6c20000001, 2969891322179092481, 13, 26, 3, 246015212717434719, 78065254858085547, (85105441*13*5*2^29)
0x2976921ce4000001, 2987736055588847617, 1, 26, 5, 814499116290532621, 1395867229455529121, (1289447*677*17*3*2^26)
0x299da4c304000001, 2998734084391305217, 1, 26, 7, 2193404549758534209, 2280611878894958909, (79651729*17*11*3*2^26)
0x29e0138ec4000001, 3017433254232850433, 1, 26, 3, 493867084350267467, 1968449104587829253, (917617537*7^2*2^26)
0x2b0985cd0c000001, 3101156934137413633, 1, 26, 7, 2090635873337008584, 521344467958667567, (31793*101*41*13*3^3*2^26)
0x2b8a61fd88000001, 3137427831953293313, 1, 26, 5, 1536091008234844030, 1238193593117611775, (3339379847*7*2^27)
0x2c16298620000001, 3176772243195691009, 9, 27, 23, 2998300564021550191, 902574819759800553, (979831*61*11*3^2*2^29)
0x2c842901d0000001, 3207733922356002817, 7, 28, 5, 1523683635041096692, 3154971583035042370, (297457*1913*7*3*2^28)
0x2ca26792d4000001, 3216246964215611393, 1, 26, 3, 1517518663274324905, 2129119363349800761, (92951*2467*19*11*2^26)
0x2d1c07a768000001, 3250481446640418817, 1, 27, 5, 1065810059449338785, 1623720257175915718, (6529*1021*173*7*3*2^27)
0x2db442da08000001, 3293330731719196673, 7, 27, 3, 113330352708327626, 2298372395216713739, (9521*1061*347*7*2^27)
0x2eeb9eb840000001, 3380970459456602113, 1, 26, 5, 997561900314377058, 2059917662335632305, (1536737*683*3*2^30)
0x311e372e88000001, 3539327030149513217, 1, 26, 3, 1203980672071061596, 105697814525703480, (497547949*53*2^27)
0x31cd9da590000001, 3588697812495237121, 1, 27, 17, 1209348937195381431, 1570138288680028516, (633449*67*7*5*3^2*2^28)
0x31e8242734000001, 3596164053250080769, 3, 26, 11, 1565827433382961282, 1196303003056152634, (1050725887*17*3*2^26)
0x328be81b78000001, 3642259928334204929, 1, 27, 3, 1443726139595968925, 3278532423853235697, (9024593*97*31*2^27)
0x335ffde83c000001, 3701956592602710017, 1, 26, 3, 2186188583595948928, 1320013042145138993, (2398410953*23*2^26)
0x33daf1d008000001, 3736564716646957057, 1, 27, 13, 1650854658436879311, 2393133708681984307, (10581367*877*3*2^27)
0x351bda0968000001, 3826892042315759617, 3, 26, 5, 2185156650844579829, 2538502083054451593, (1059671*8969*3*2^27)
0x3730f281e4000001, 3976945110658056193, 1, 26, 5, 2993732503061540936, 1039955707259381352, (19753700051*3*2^26)
0x37bcd30b34000001, 4016317012778156033, 1, 26, 3, 465041681940351762, 507119766593844459, (27197*17327*127*2^26)
0x37c62feb48000001, 4018952405046525953, 1, 27, 3, 1802636177853445231, 3729246111913317172, (14845577*2017*2^27)
0x38b70d964c000001, 4086750126033338369, 1, 26, 3, 1236222603584416280, 3528491310214083276, (1409*1229*139*23*11*2^26)
0x3995cfeabc000001, 4149451238775193601, 1, 26, 3, 2773114793432805883, 2137113916727713022, (70853*521*67*5^2*2^26)
0x3a25874234000001, 4189903746748121089, 1, 26, 41, 1997758893125550556, 92971526868374832, (223779323*31*3^2*2^26)
0x3b84703054000001, 4288676098033582081, 1, 26, 13, 4087210687920489658, 3864104511162925379, (608630989*7*5*3*2^26)
0x3b9e52c790000001, 4295962111625920513, 1, 28, 5, 1278672322965972673, 1588269684189040326, (386647*73*7*3^4*2^28)
0x3c8d9159fc000001, 4363303429657853953, 1, 26, 7, 830487614483445701, 3435199924203284627, (3433037*107*59*3*2^26)
0x3d4853f504000001, 4415871746435973121, 5, 26, 37, 3165491059413527341, 2004072930527956147, (92507*479*11*5*3^3*2^26)
0x3d68485748000001, 4424866173598826497, 3, 27, 5, 3222940107848139080, 1956734948064434138, (10989274019*3*2^27)
0x3d8c0af1c8000001, 4434931766611935233, 1, 27, 3, 2481622260952398909, 3091977614176773732, (1135531*4157*7*2^27)
0x3e08fdd1a8000001, 4470101707073781761, 5, 26, 3, 914378621753178986, 3145105531751226428, (269141*24749*5*2^27)
0x3e2eb5c6b0000001, 4480718544241164289, 7, 27, 19, 768648899009962081, 1836497973012950493, (10301*89*17^2*7*3^2*2^28)
0x3e9dd6954c000001, 4511998338408644609, 7, 26, 3, 1737434714250511834, 3611972301602738930, (9604859221*7*2^26)
0x3ef166f03c000001, 4535519481723617281, 1, 26, 7, 2981000636658545702, 3851560279867545994, (2273*857*257*5*3^3*2^26)
0x3ef71afcf8000001, 4537124823393894401, 1, 26, 3, 3624280287339433243, 1763783591557992766, (1979749*683*5^2*2^27)
0x3f20ebbbb0000001, 4548894814988402689, 1, 27, 7, 4281543534721332498, 3107376785910416954, (63463*29669*3^2*2^28)
0x3fae7cee80000001, 4588742434128658433, 1, 29, 3, 132610359250039243, 3762940913832781428, (194254519*11*2^31)
[/code:1]

Guillermo
gbvalor is offline   Reply With Quote