Primorials

When one is generating primes, the first step people usually take to see if a candidate number is prime is to see if is divisible by some small primes. You could try dividing it by a selection of small primes (which requires a number of divisions, which are generally computationally demanding operations). Or you could do it in one operation by calculating the greatest common denominator (GCD) with a primorial, which is the product of a number of primes, and the GCD will necessarily be 1 for any prime not used to make the primorial. To be computationally efficient you would want the largest primorial that fits in the number of bits your computer is working with, for example with FFA you want the largest primorial that fits in the FZ field size. So I went ahead and calculated some primorials, it just took a short time using FFA and the peh tape example in FFA Chapter 18C.

The largest primorials of power of 2 bits from 256 to 5196 bits are (in hexadecimal notation):

256 bits:
024776FFD3CBD21C872ECCD26AD078C5BA0586E2E57CF68515E3C4828A673A6E

512 bits:
20D553F6EC8DF4DD610278518BABE13E0EFD87744717F733836C634407D0230E
467B622F9787080ADDE08CB349423BC93EFD965375B51F301BD9D9D25C61891E

1024 bits:
0590BFF0E1E497D01EC56374D8417AE5706FDFBE24240DB0FB6AD6FAD3F49804
3820F879440DFD1F4E101DEAEDDFF905F3621EAEA0CAD6EF2962D5FAE132DD23
5DEDC15A2BD2360E3593649B3164675B0DDC0AAA31CB1CACC71DE31758B8E996
6B776DCBB5C4F07BA3819CFBD89F8E1CA30DA823BE6C6D1E0C3546C023E602F2

2048 bits:
48CB4F7B0A023C393C0A4F253FFE4D1905DEFDF482D0C7754B59B612E3B74199
587DC933268A053E59F021733C80D558BF9CBBAD3A38E2FB5D4BA3157227E8AC
A0ACF379238AFA8DB31110AF0C566DC5DBC5C8E783E1566B3B44A4E35FFC2BFE
481C533A1609E99A1C9AF81C8F634F7400FBD1355D091FAB7B9AFF302AAC9D60
C15C29E3396A18523E177B1DA3898FF1F8BF74A2CC40032736A65B25B5908950
863A8019065A073EBF20164F14EA4338530C2818F208BAEEB2A810A9862A09B8
ADE3BEBDD7CF7DC88ECB1722F7ED2DAD24FE5C4851F7D6681CA2B97306BAC70E
37D177C139E2688AF33E5CCEF102A2AE35276983DDCABA3720E5C165EB88C0FE

4096 bits:
12C40FF99633ACEB1C6E97DCD86E135E14A953057F2029C8A16E9030276E60B6
984BE1C5D4DC56ADF23CB324285A42DD5D65D9C00BF41A31DFD6F1DF8683E63E
F07DC8958BDEBBFC6AAF2250420C2AD8C9A2CF4A8439FD867977A7107017D0A8
293F6CB811CF39A09D89168AC51DCCFEB8DF603031F43FEE64481817638FFD82
98904698DF87C0EAEC9EC7804D06C3063B12C1E49646FD2D85957498344247FE
674937947293D1575BBC0DB58AE07A2DB6ECEFBE5619C58F090BD7ABCD37B014
309153FC51394574CC94D0F67E0A802ADCCF5CCED3813C239CACE6AFEB4AED49
1DDBB2C66BCC50EF8E74CA8116E2909DA1E23A41AA3D1CA8CF43C98137EE5374
2D3F9FB7516AB898B6D05F5450E3373E937E6C5B3E07DCD7BCF203D281C49368
392773560A9579562135E2554CA6BDB1EC4757FA6255541094E91F0CA70779C6
2BB81A8B9712A11BD95277B445E1CEF49FD5454F21C01CB5B5377735CFABF6C6
A944A5B4FB84DCD585AF4C85D57E9025CC95C32B7E53993DC04B096EE9B96225
22AF7EA4871F6F6F9AD4F0494E831798CB060B1D85E0D251C884C46F316A07EC
EA3B9DC5803E735961F68F1EDD162D461FD043371CCE098E4D6C07C20013ECEE
EC8CA282AE1A96985461B70804DF269703E1ABD30B92EBAD520EB483A82F8DB3
279692E797CA254CFB663ED5D91987D3CBD7B83D6F68E8A8A2A542ADAB58B0FA

8196 bits:
262AF01F3648722B3F74D7AD98C2C516AFD847B1EF36681D88C8A267DB62DDAD
67A70C8056653695185F2F0937744D6AB86DA6F3D760DD2057461B788EC88E71
5F21C1B783E408B0F16ED7659EAF90BFF6D1C2406A317E5F1BEC5027639D1C9A
E46AE37E75A64A39B0659B20EDF3E37F0C6AD2796BB7A50CD2EC9CE73A3D560D
09F74F6058DC7516585FD70D5D96E357D70AD3134C9B0416C60C6E9927CDC5C2
25B2DB5243E27DE1FD743D3176EABBB0795D92D16D54C730BC3239D673F37B7E
7DD96DF8131A822600FC4671BF7C8124B39D78CDEF30F15B29CAEE8FA3E87B7C
7E578BFE0B2AFFEE22673E01617BCE281BD6D52A9F2C9439E0C51321B9601146
3EFAB322DC963BAF11DC6D182E43E7E00F6DC90CD33DF130AD1ADA95DBF98DE0
CFC3E8FA005977B0CD6630A6F687B9EFDB65B88A56148BECA064359F9F3E2BED
CDF86393C0C9477DD644BAFCA1427AD73C12AF01146FEE7C8574FB056BDE80CA
74C4E8CAB624018A74BEB1060DB09048E519F1BE604D29AF45D3F0E7BD32097E
9C64C3A1BD9791375F071CFAD0098E3C636163A1E0B08A2BB415A439B872303A
050A7562D11700CF357852896FB2B8581BE532199296C4AF7AB83068A9C7EE82
01B5643A135ACF3619995306B554A2DDC0A7DCEACB61ECAF8F857AD7F5DDA0C7
788D9279BE5D497E745BF83116FC59E58FB98D2CF364AFCD690E4B630A50BD58
08224F03F6BB681242B8877CD8E0CF1AB7FFBA13C87922E143A2FFB4152C20D1
EB2ED07292CF862C6AEDE0DDCD96265EED26B5C5718647EAE32802DD0F9054AE
F30F2F6EE2F42C146357AC275F28C7AF5F9AAA52E85029128FFA14CAE574D63E
C1CFBDBA812E71BF4A8A1C46DF63467F5FB59F91629DAB2755E4814AB3093E33
5CB92827BA01D0BBE938A661C1BA6D520636BA6EA3A6B8FD5DEDC2758BCFDA08
065FFC7AEA152F84DF76BEAC03234AB8397CC685D551F3249B0E2FB2394FDB60
2060FCFB75348956F12317640E5D59AE12A857F32CDC04E26541725291071C33
8FC932AE25449D5070500C6DE46BB450E08562D7184BA06627417106AE9E18B9
B3119D78837CB5FA7B28AA028A35EBCDF04A69536425815F7D44A27CE9DB64E5
EA927480586ED1C535B08504842BD4B54140C2860D13ACDE54E4851756BAB54F
2FA694F5C41DFCD70FC541C31C57A2AE28B03BAF3F05113190AE9A38567A69F9
42CAF0515086294B1CF4BE7765D41E84BA1C0D983B4C8C89597229005EB768B1
12F7C0F2542BE0A676116A1E3D238AF0B244A579977C6E0F8A832B078FD078BD
23C90EDBA6CFE7A1E71CC9F7E23057EAF3CDE1A11579B3020C5D46B7A23E8C5B
2777C77DE467487387712191E7B50B03624DD79E65F227BE767D990DAF990DBA
2693014B3EE33290ABF2C8795120E85F56B5FE65C87BB8325C05E34FBCAE69F6

16384 bits (this one took about 10 minutes to compute on my computer):
084305A6181B54747927A368E1DC7AC9D49C8240CC2BF1F209A8EB9F82059332
F13F84CB081FDE7A2BF1470012A4AE1C8F7FEFFB6A69BCA24A30FBF314936253
AC4CFDEA2D4C53C0B7060E380E8934D08CAD14AEF351072D573A7FB75FBE7289
42D3C1440BAF498ABF7263C00B94D024F4BA329D47B29940390C228552C0708B
6977E7ECF943589B9357B54689BE7F92F94381841FD34C6A88CA2C8B8967551B
A253BCF494F32DF826DF59E26BFAFB65582E34D8F5D1AB58422E62A67F23AAA3
BE152E247867F642F133AF9ACDC01FFD9DA2AE2C6DB4116EEF1EB591E2C756E0
432F4293D59E086EA1F8F39884E2F0E4B762E0B1BCCE295CE301120254DABCC2
1354419FEE9A6ACE43214355951CEA8DD71F51332812F9D953BD88E4920AA278
981B4E9EF9678A756CA4AF66900372A4C65B62BABD491C317D049C95F7A188E4
1A9704B429C811D554776E67F2C38D309533FFA0397C815F755074F51B49B7AB
267354D460771ECA980F84D778485FDE3A8FAAE91F30A26D9DB963576F49E7A7
F58E9ABC68180C7E021DFF49CC1AA00A99C2404FD9A99CD78E23B70AF4278AF4
DF1233F36985B9E6078D8BA003E32B56623FBFAE665D9C941C3ACE5C95DF453F
E30174FED89611CF8C296F16014BB3B68FE0D1D979F1311405DAE6B4E58516F3
52189CD2D3667780D87F164A12823D66DF92A3DE7D6B42FF4DE6FC693B7AC771
DF6F6F37975630A18DDEDD56DCE7F4D52E14F94F10128CE1EF46CA87CA9A468D
8D7853B6DD1AB5ABC42CD895E2D0253FEDA807DAD86CBAD3E5CB34C2B5F825CC
FE830D92474CC782D7DD44D7364FC024F8CF83BF4520AD42E248103C17B53372
24031FFC9CFDE17D390E057030288C5E86821CEAA8899C138DA25FF4C9FAFD0E
5A48401D5F28297F9EE6D05BDC41BC947DA353D87B099D1E7E41E8493E981A4B
989BE3E43F5BD7AFED503FEC31EEBB31F7D6E0AE6DFADA1EDDAEC42EBFD15A90
BA36C4A031E2E4BB137EFABF07D4060097BDDDDC6C0D8A1CC7289724382ECB37
D092B8FF99695F9460514616039CFACDC1D706EFBF46EC7F8C3F70D00B903AFF
4155F7659E48FE46CFBECB4A2943AF1E0D9A77B9434DDB5BBF712FA0B0E83F8F
794CB7326805826669B674377032F0B81B488DC58FF85585D6DC51E0141D2E54
BA619C5E4150609B5319B84482F4865AB68307087C61C1CD98A42F2B4F9F152A
E248D0FD894B7DF1DD1AF1386CEA4AB51A8DF94522C216A338688D9AA8759F0D
8D560FE77CF72182345E37084CB1680F1F3A48C8E8A1227397C2DB4708367708
5DD15A2C59D4DF6CDADA456E17D08D96B366E4B8415F6BF70CD3A30F9AA46ADF
FB60DED2D09AB4840ED7A0189EF3EDFA4205CA1FA5B31D75A33D136DAA8F5E42
BA96119F66FDAF64A0EE4E293802F77F50315CC8B1845F9846462639F87C8BCE
5D83014EA238002FA238919E91187D8BC547FE17AB24E2EE7041672BFFFAE649
D4BC1FEB896AA74D1D8B65D9F72A4574FAE40B44448150327355FF987DDB6C42
94B60C4C0AB94D449E2D824B1191BF5E22DCCFE4C47B5728B404969DE964E872
0762BF5694C123D1DFD7BFE4F8F08DBDC6D9032451A92C7844ABEC494B1FC861
E141B72C1B31BD496027991C8638A3D94F8ED1FEEAE574A00DA7ACC993C84E62
0FA558D5EC9BBC4B6B5FC7AB7D416A26A55DDFE990BEA7B4F8A99D3DEA9B04F0
EA845911B72861D76F9E25E93AAB7BDF470577F9E70EE73300CEC6ADA14368DB
908B61BEF8BFD7CA691566E95901D95A844B9888B2937B990C08CBD76C4471A9
4285545BE1E13B77357872741C831F6D433C98696A47BD556DEBA9B0E64F9E69
AB2AE0E55AB6CECDE0FF48EEB47594D1B8B25DC9AF764C24CD978B78C3A8A37D
5068749063F92A2110B74A6E9607103EC9857D4F1C5797BCB9735501B699A690
3BFE2FD7A33CFB78B3E146755BBCF133268C643BB10D6C01ABC7537DCB050498
F565BB4C18C7671FBF1C52686C054A8FC15275E034932F4F4A03CE1F1A0C0283
901FA0949A00000E6537AE7C6E5812CA40B2F8ED8513757166426E18D2DB2DF9
599C0A2E23C61C8FBF04547BCC05B1520B8B1D71B7BBA1508F4CF973F5A27776
3C0475D6611E942FC3BE37C3BB003C826F6593204F7335EFB98D3A5BF1BCC242
0EBAF3C8B06978470538F91DCFA10DB3E31BF8064361621194DA8E52F6B30C6C
68C84A63F2C73C687149A3A33802A5112F5A6B2FA3A589A7B7EA75306637896D
4A22235C0AECCD57ACB4A9CFED3BEE57CEBD2D3B812A64AC701E2DC092AF3DB0
268508BAC8CB4D1F27BFCB9DDAA62DFA6880B284E2F2953394EB392E635100D3
A6D087E52844870F0DB3630A103745E471EEA4C1B31FBC4B2B064752FC6E2171
45E2D7A451EE4CE1E2BBAF080FF94B6F39D41368859775EE1579C92B489C2C4A
488EA478CC504700CCDF57F8B38B8C7D54584163891139868406703CBB2C26AF
E66220F3DA607F499618FEFD1E1CE37F0A688A72B2E622AAC82F769E6A1E9EA1
0A2E76099DDA01A78273A6431AABBC2EBB0246A4266672C6EB67B6F9BC4E5C84
736BEDE20E9335001E8BC0440F297EC367F1BEC6F9C58825A7D981DCD15029D5
F84D6B17FB87EA5E352F5D7E14FE9CE5D08D9A0D3F020067EB09B9D2AF58F627
C18D43224D4B3E319F91CA7281FD2488BCBC310C06B76FABC7E4D150C0CB14B2
71C1F78BFEF2941F838E460B11B2A9CD5F83FC7940E1D0A3C95D6166AC5350F9
7B6937A09986F4543AA96AAAE5B7A7CEA33A13DC2176337C4B0B73E6C5FD12C0
1D2684F78FCE3F2766D40A5E7F4C075773B223D7B9D77B678ED99004AAFA0FC2
80F6118244F1FE49743B761C6D1C514258DE356246FF0037D401FA7386A2C252

Tags:

One Response to “Primorials”

  1. Note that this approach only wins in FFA or a very FFA-like system, where there is no such thing as a "small number" and consequently also no such thing as a "fast division by a small number."

    In heathen bignum libs, e.g. GMP, the trial-division-by-smallints can be faster.

    And at any rate this method is only attractive because, again in FFA, Miller-Rabin always runs in "worst case" time. Which is why heathen numerics people were never much concerned with optimizing pre-MR filters for candidate primes.

Leave a Reply