Let n be a sufficiently large number. Compute (545925250 >> (n%30)) & 1 , essentially doing a lookup into a 30-bit table, testing for divisibility by 2, 3, and 5. If the bit is 0, the number is definitely not prime. If the bit is 1, the number might be prime; test further, perhaps with Miller-Rabin.
2 bit lookup table: 2
2*3 = 6 bit lookup table: 34
2*3*5 = 30 bit: 545925250 (a number that is somehow related to the Exceptional Lie group E8)
2*3*5*7 = 210 bit: 823772507696191300441957393277285052703670143885717441398581250
2*3*5*7*11 = 2310 bit (number is given in hexadecimal): 20 02288282 28820A08 A0882022 8A200088 28028208 A20A00A2 8008028A 20A08820 82822822 0808A208 08200A20 A0822882 8228200A 00A28820 228800A0 8A088200 28A20208 82882820 0A20A08A 28028028 820A0822 08282282 20808A08 808220A2 08082280 28228A00 A00A2880 8228820A 08808820 228A2020 88208282 08A20A08 A2802802 8220A08A 20820228 200808A2 8808020A 20208228 828220A0 0A00A288 28228820 A0820882 0228A202 08808828 208A2080 8A280280 28A20A00 A2080822 82208088 28808220 A20A0822 0828208A 00A00A28 82822802 0A08A088 20228A00 20882882 8008A202 08A28028 020A20A0 8A208282 28020808 22880822 0A20A082 08828228 A00800A2 80282288 20A00A08 800228A2 02088288 28208A20 A08A2002
Divisibility by 2 is easy to check by examining the least significant bit, so only do table lookup for divisibility by small odd primes. Tables below.
However, largest 64-bit "odd primorial" is 53# / 2 = 16294579238595022365. 32-bit is 29# / 2 = 3234846615 . First calculate bigint modulo odd primorial, then do trial division with machine register-sized operands.
3 bit lookup table for odd numbers: 6
3*5 = 15 bit lookup table: 27030
3*5*7 = 105 bit: 33143151776325075711432218847510
3*5*7*11 = 1155 bit (in hexadecimal): 6 884D125A 6530C369 969324A4 5B44A299 2D22D861 B4C34896 5229A253 4C94992C 30DA6584 CB2916C1 29A60B44 B6184D32 D2658489 6894D324 A65B0836 196930CA 05B44A69 92D32D06 0B4CB499 6522DA05 30C96986 C10DA652 4CB29169 121A64B4 CB2186D2 2D065948 36894D32 1A65B0C3 4992932C A45944A6 912C32D8 61B44B49 94522DA2 524C9699 6C30CA65 A48B2116
3*5*7*11*13 = 15015 bit (in hexadecimal): 68 80D105A6 53043699 69324A45 344A2992 D22D861B 0C348965 221A2134 C94892C3 0DA6584C A2916C12 9A40B44B 6184932D 26484816 894D124A 65B08321 94930CA0 5B40A699 2C32D060 B4C94986 522DA053 0C969864 109A6524 CB291691 21864A4C B2182D20 D0659403 6894D320 A6530C34 992922CA 45904A49 12C32586 1B44B489 4522DA25 04C86996 C30CA45A 48B21169 109A24B4 C26186D1 2D264948 B2894532 5A45B083 6986812C 24534486 98293258 21B4CB09 96522982 534C1681 6C309865 A4CB0912 D109A649 44B6106C 32C26114 0B6894D2 25A65A0C 14996932 4A41B40A 6092D30D 82194CA4 996522D2 0434C961 96030DA4 4A0C3290 6D129A64 34CB2184 93252659 48B2894C 225065B0 C1688693 28A05B44 A4992532 986194CB 4916422D 82124496 990C30DA 65A44929 16D128A6 4348B618 6D20D225 908A4894 D325260B 0C368961 32CA4590 4A6982D1 2D84134C B4196122 5A2434C1 2996C00D 865A4C32 814D129A 64B48B41 82C32D26 59489680 4C325A21 B0436994 1328A45A 4486912D 32C861A4 8B419252 0DA25344 86996C30 C26424CB 29165029 A44B0CB4 186D1252 61148B68 949325A6 590C2299 6922C845 B4426092 9329860B 4C349925 02DA2514 C92914C3 0DA61A40 B2914C12 9264A4C9 6186D32C 225948B6 0945301A 25B0C269 16932C04 4A44A699 2530D841 B04B4986 502CA253 4C969968 205A65A0 CB0916D0 21860B4C 36086D32 9265948A 4890D325 A4590C36 116832CA 40B44269 90D12D86 1A4C9099 4522CA25 34896196 C30D225A 4C82906D 129224B4 CB618653 29245908 B6804D12 586520C3 69929304 A45B44A2 992D22C8 6134C348 965229A2 530C9499 2C305A61 84CB2816 C129A609 44A6184D 32D24584 89609493 24A64B08 36196910 CA05B44A 2990D32D 060B48B4 996422D2 0530C969 86C10DA2 524CB291 61121A64 B4CB2106 D22D0658 4836890D 301A65B0 43499293 2CA45144 A6912C22 D861B04B 49945225 A2124C96 896C30CA 65848A21 16D109A0 4B4CA618 6932D264 94836894 5125A45B 0C329849 12CA4534 0A699283 25061B4C 90986522 D82534C1 68964309 A65A4CB0 912D1298 6484CB61 02C30D26 1940B689 4D324A65 20C16996 922CA45B 00A4192D 305821B4 CA489652 2D22414C 86996430 DA45A0CB 21069129 A6434C36 18691252 65948B28 94D22586 5B083689 68328245 B4484982 D32D8219 4CB49164 229A2134 496914C3 0D865A4C 92912D10 8A64B40B 6186D30C 225148A6 894D2252 64B0C349 961324A4 1B04A688 2D12D861 14CA4996 1225A053 4C921968 20D864A4 C32816D1 29A64B4C B0180D32 D265948B 6814C325 261B0416 984932CA 05A44869 92532886 1B48B411 6520D825 24C86992 C30D264A 44B29165 128A4430 CB6186D0 2D265108 B4894932 5A61B0C3 2896922C 84594426 892D3298 41B4CB41 92122DA2 414C1691 6C10DA61 A44B2914 D129A64A 4896186C 32C26594 896084D3 05A25B0C 26996132 8244B44A 6912532D 841A0CB4 982500DA 25344969 968304A6 524CB291 6D029864 B0C34086 D3212619 48B4890D 325A6590 C2691683 2CA41B44 A6190932 D860A4C1 4996502C A2534892 194C30DA 25A48A29 16C12926 4B4C9618 6532D205 908B6884 5121A653 0C369169 324845A4 4A2992D2 0D861B44 34896522 8A2534C9 4992C20D A6580CB0 916C121A 60B44B60 84D32D26 58488689 4D324A45 B0836196 930CA04B 4426992D 12D060B4 CB099452 2DA05308 96986C10 D26524C9 29069121 A24B4CB2 18652290 65948368 14D32186 5A0C3499 2930CA45 944A6912 C32C8613 44B49945 22DA2520 C94996C3 04A61A48 B2016D10 9A2494CA 6186D32D 244948B6 0941325A 44B0C369 86912CA4 5344A299 09325861 B48B0996 422D0253 4C16886C 309A25A4 CB091251 29A6494C B6106C32 D061840B 6890D305 A65A0416 996932CA 45340A61 92D20D82 1B0CA499 65225220 34C96896 430DA458 0CA2906D 129A4434 CB618693 25264948 32894D02 5865B0C3 28949328 A45B40A4 992C32D0 6194C949 06422DA2 13449699 44309A65 A4C92916 D128864A 48B6182D 30D22594 0A6894D3 2426430C 36996122 CA45B04A 4982D125 86134CB4 8961225A 2514C829 96C20D84 5A4C3201 69129A64 B4C34182 D12D2659 48B2814C 325A61B0 03699483 2C245A44 86982D32 C821B48B 41965209 A2534C86 916C30D0 64A4CB29 125109A4 4B04B618 6D12C265 148B6894 9225A65B 0C309969 224841B4 426892D3 2986194C A4992522 DA0514C9 6116830D A60A4432 914D129A 64A4C921 84D32C26 5948B609 4C305225 B0C06986 932C204B 44A69925 329841B0 CB490650 2D82524C 96992830 5A65A44B 2916D028 86434C36 086D2292 65908B48 90D325A6 190C3681 6832CA41 944A6990 D32D841A 4C941961 22CA2434 816196C1 0DA25A4C A2914D12 9264B48B 6186432D 24590896 884D125A 2530C369 961320A4 5B44A291 2D22D861 A4C34892 5209A253 4494992C 30CA6504 CB2916C0 29A60B04 B4184D32 52618489 6894D324 A6590826 196930CA 05B44A61 92932D06 0B4C3499 6502DA05 30C92984 C10DA652 48B29168 121264B4 C92186D2 2D025948 36894532 1A65B0C3 4912932C 845844A6 912C30D8 61B44B49 94522CA2 524C9699 6C20CA65 A08B0116
No comments :
Post a Comment