(----------------------------------------------------------------------------) (----------------------------------------------------------------------------) (- Demo Tape for 'Peh'; random probable-prime generator with multi-part -) (- split primorial used in GCD litmus prefilter. -) (- -) (- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) -) (- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html -) (- -) (- You do not have, nor can you ever acquire the right to use, copy or -) (- distribute this software ; Should you use this software for any purpose, -) (- or copy and distribute it to anyone or in any manner, you are breaking -) (- the laws of whatever soi-disant jurisdiction, and you promise to -) (- continue doing so for the indefinite future. In any case, please -) (- always : read and understand any software ; verify any PGP signatures -) (- that you use - for any purpose. -) (- -) (- See also http://trilema.com/2015/a-new-software-licensing-paradigm . -) (----------------------------------------------------------------------------) (----------------------------------------------------------------------------) (----------------------------------------------------------------------------) ( Number of Primes to Generate : ) @Number-of-Primes@ .8 ; (----------------------------------------------------------------------------) ( 32768-bit Primorial cut into 2048-bit factors : ) @Primorial_01@ ( Regs : none ) .48CB4F7B0A023C393C0A4F253FFE4D1905DEFDF482D0C7754B59B612E3B741995 87DC933268A053E59F021733C80D558BF9CBBAD3A38E2FB5D4BA3157227E8ACA0 ACF379238AFA8DB31110AF0C566DC5DBC5C8E783E1566B3B44A4E35FFC2BFE481 C533A1609E99A1C9AF81C8F634F7400FBD1355D091FAB7B9AFF302AAC9D60C15C 29E3396A18523E177B1DA3898FF1F8BF74A2CC40032736A65B25B5908950863A8 019065A073EBF20164F14EA4338530C2818F208BAEEB2A810A9862A09B8ADE3BE BDD7CF7DC88ECB1722F7ED2DAD24FE5C4851F7D6681CA2B97306BAC70E37D177C 139E2688AF33E5CCEF102A2AE35276983DDCABA3720E5C165EB88C0FE ; (----------------------------------------------------------------------------) @Primorial_02@ ( Regs : none ) .41FEC1AD0F02CA1C9023E5426CA4236D7F657874A303ED03989F289EF723A72EF C113DEE100CE1F8DFFFE8BE9406A807FC44C2025839C6C1183C10511A321DC630 D8447877CE88310A1CDE9629010F1E6FC4F3F81989D4A955F7E93720E2FFDCEA2 71230D34A0F04E8396D6DC034AA8C693EC3F4919E8CD2FCFD22451E736D43BA0B E213E2D3BE8F8E57F76D0C02BF034335CA1578DC2415975AC60089FA391AC7953 6CD9EDBA00F9E2D4CD26959E345C441DC5FF82982E23FEAF9C4CC7C030E44412C 16FAB98FBDA11F908381BE24C5059DDDDDB300671C7164D687F404419F7A74ACC 5BBBE260AA1493419174E58DCAEA1244605E2A10F7C3D9F27BDA54903 ; (----------------------------------------------------------------------------) @Primorial_03@ ( Regs : none ) .08F2735927E4F275486BAE6C9CD9091E219D7672E14BF83CE60CFC04F78F1B7E4 A68BD79E5104A5B97241336D8BCD20B0F5DDA3CDAD355FDF438445DEA388AA02E 07DCE328698B8CE8881C8942514F26B611EC0236A7F72D41C6165797148BA5A4C C1AAE0C373644AD1527E3289153B4BC9AC72C9669C099C3A28B184A3932C8AB1F 07E46D00B3D605CCA7C748F17438FCEA82EDBA41EAFA7C5BD641A70E362FB4A11 AA5B90881FD36E6B98BBA8A634590FAF9BE2EC9943D8F07F7A3E597D44E6B0842 2FC00467521EAFBD3EA10A372BB369F3FFA40BCA5335AA2BB24FC21BB70D7B9AA 970E95ABA75FE75781693B58FD4F0426074B93D2A500BFFD07D572D59 ; (----------------------------------------------------------------------------) @Primorial_04@ ( Regs : none ) .0293F44C7E919797CBC851592499EC41C2659C01449EE9BE233972C056754EE881 BEAD5591259CB8774D6E75B42AC0F949236B154FDE4936257C03143061CFD06912 622694AABD94ADD2510AE2044D985A78EAA734C64AF65B626D75AE40AE4510FA73 08CDB0D8EE00662B763EB80A7E566F9ADA5F297BE4F71971E65123532C9E14CBCA 221BAE9A87B2C8D333A2921958FA043D26EF6B6BC0694DCFC6FAA577F2A7B2A299 1F6EA4B611EE17F3700C5FD3C76D4F1085F0B1531D3D138CC5518EAA25DF02767B CC32CD6ACA4F99FE6DADD24FDD89B4357BCF3DBD6366309627CBDED685D6D58E1C 2A5C61325448A73180754ACB32DA69A57B669FC1E001BC31F5 ; (----------------------------------------------------------------------------) @Primorial_05@ ( Regs : none ) .002EAE9FF7F388947EBDF1F2F77AA725D9B8EF9F3DA5A8604A64A95E9A1BD645D4 D131A2553600BC0FE2B197927A80469F40F42E74853D6BDB391A1B472534ECB7AE C70A56FF6F82CA28D24C5EC7F825FBA1D1D1E20904E501743A239EFEA0F3CF16CC CA831E2E376703DAEC02BFDD321C4818CC3C355E160F11BB0246487E7D35D18D05 2414679E4F9B8ED33C9DBD972D81E7FC1853A391C994C9549913B831434C093585 415BB26C0ED7E779BE2BE979CB74BCAD2BF29176397CA67710808A5AA156DE90AB 2DC4CE407C076E730F2F2B7D50BF37645C9EF835A3124C958DAF759B52213F4CE3 2666D7E48C143DB7FD85E3DA795E2540E157FCC7BEA31169D7 ; (----------------------------------------------------------------------------) @Primorial_06@ ( Regs : none ) .326C96C47689A8EC9B1269928F41C12B19CFC807214CEAAF36D4C2617E73D42FC5 43F87054C71126E3385CB5F468E4C45707692D4444E71D3AF8553A56B174F96E4E 8DEED500BD271492BBE5A3435E4747101F2C2D81FA2F987226A7FAA61441DC6D59 1D39112B7919AB88B490CB847F89B61D188F8F2A1E05F724F4C8F104FCF079A341 21F4156B499FCEC9A835209C9E4D186C6968EC7488B0892659C01EA273BE8112D2 960D9DC693C9F32B8B80C19A353E5CD047AC5AC1DDEC379D4BC0827B36B1E91316 47FF854F6D0BE099D88651421815DD33515B8B7A43129740C45E652CB2AD5462E7 82205BE946E5E200055FAD3D6754FE8AE849331A1DDBBCDF17 ; (----------------------------------------------------------------------------) @Primorial_07@ ( Regs : none ) .0B726FED100076D810395D237136D1D8F0BBB5F8C757650DB61852AB68838D69C7 C6B94DD6CF48992351AC285F268B39827AD522267D9740050B4A9B58B4213E87C4 AD7B449BFFA1A413571A9B72188B555AEF27FA26380686285AD4FBA64C56542A79 D7D1642DF08C909BCB1C0FBD720CAB5B76BB1F7E76AE408C107A6C466D7F81F2C5 944E96A9EA9894396B6F62A19272DC4BEF60F55DDA1ED197AA3D937798DBB303D7 0D3B4DACA0298AA84E28D8D600E47E3117560AD67225D80A745074F51F912C7B1E B0A65BB45ACB3EAB6200978BCD93341470D0BDA18EF7D930A47A5B7B4227F8C5C0 89BA36997331D585F30C1AA14D6F3D010994871DDB767D5825 ; (----------------------------------------------------------------------------) @Primorial_08@ ( Regs : none ) .00089EA6CF0D722178325A6EB902CA5260DC833308143AB31264C2F67039A65795 1615C03745B710FA69F0CEC14B6385597A626F520E3748C3D17A74B0D29B8EEB50 B5D8B3B91C679125DBF77E0FCEB5F44A05A8D6D0D03E3E85DD004B04F6B01E4E47 1383D213398832273A68077F22DB3EAFCA8E2ABCBC6FCC2247E773818DDF0BF31A F647CE5EB983E017A9FD2086A766FD4B207C6682DCC4A32DD178C16F9ABEAC40CA 019251F608AE490DF5F7726D0EF20F274BB02412509E0BE51D24B9771BBFD9557D DC8420A081A12BBB5807C25ED9A528B1850B2422471B8D0D14688AD4538AC8D33C 6EADCDAF3B672F71EF2473F6F31C5CB641A79D57A6CF74EFBD ; (----------------------------------------------------------------------------) @Primorial_09@ ( Regs : none ) .000E4BB697EAFB6976D31535880A47A0A5077084E314E3CFD90817A55BFCF0EA65 CC480903597D453FF826DA67733974625AB997327A4E2CE5A47F6C812999C6E043 7A72863D856E1B5241F46088BFA793213E229599AC0212175F57FA2CF836D8CFD5 D568FA70825F6D2358D3EE8F8E1968BEEB95774AAE18CB60393815BBB2D0C46998 B1D2BFA2B4FFD5F10380764F70F23654D38B052C93329B4EAD03B64168F693C713 BF9CDAC9C821260D86E67755936C206EC81D9B7530FC5C9B32052B9CD9140B3C2A 8C122F2168E9267567FD5D99CDC3830B9F06C3088AEDEF81655203CEF6BC202395 C5AD6A926F17B83F8E38B8BAAED4CFCFF3943A238EF83B534B ; (----------------------------------------------------------------------------) @Primorial_10@ ( Regs : none ) .2F92728EF9DA218FA4C7D0A4A98EDBF48218D27221D22A20E01D0C61BD61328906 711F506BD2C363AAFA40E1B5403D4F3A0558DCF53736315C8FEBB35F96073F2D37 47FC2CD3A5CFDF35A7EAD6C7D643E4F730667322FE53565550759C508A8193BAF8 C537548ADB4D195DC277D02BA8FB26855331BAE81E33A4FCE9DE6AF859EED5B249 AE91A647647A5BD267E45D946DA4DEB3FDFF2C1B830FA2B11A9421F493FD2F5166 5492BED57395A875F986981FC0F3AAB4A1A1798B53E46F84F62FDD63725B936176 85E7AC124CFA9E8353CBBCCC1DDA666C45652E893475A7DB09EC6B6A61FCFB9516 AFA1B3EAA6B97A462889661BE4207CC9526B29E224BE404CD9 ; (----------------------------------------------------------------------------) @Primorial_11@ ( Regs : none ) .00ACD1732973FA127CBA74F863C3EE9F4C0752AF92A7C231D0D71C4B3B8021C8BE D0EC6E0AA0515748B86A59C70496D97E51F759FFA27CC1C58A9B2DA45B562B97BD C5061D2A85C8EA7A4C06FD86F954EEC4FE95D7E620A7090169FA978E6BAAA4D1C6 05CEF1FEA44253558EC79BD10C7BD6204925C162F0D818BE2D269A591A69C21517 C6BC346A6A37D6FB81455247BC05AAC3FEEE9F9F8DFC229A51C2A40C245A526B6E 14349390B2CD9A9EBA66861BC7B2C36B21FD3A5BF882BB1CB983F821537605AB24 7A4B7BF032E000D29AE1C78F5246FA47BAB7860F8A400F41837C1D0D650344FE4E 89D7110DF3C5FC223970B6D1D356E0DDDAD32FC1F191310F09 ; (----------------------------------------------------------------------------) @Primorial_12@ ( Regs : none ) .12E3F7A40CD2102D105C14EAC260F2024976EB7605D52214ACF41D28C68A3372B3 720CDC2CB1B18F34C637024DE95B53AF5FA9C2C8F3000941BA27124E4305B21072 3D97E5E53481C66F86732C579E4CF607B468AAC087B63D9BB83B5FE88B33C0332B 53F9CB3ABFF3262B47C53D4A9F885768AED25363B78E3D284789B942E940DD971E 69B6F2ED76FFC8D5FEFE3D72928B3B3E28744158D00D250FF646FFF8633CDC0151 86CD7098BB525B4FAEE760E1127B79B5989E867A7D6D9DD0B1E68C9676BC3F6687 CFF519806A06C24FF0AA0EAEE542D4CD2E804F60EBB8FF48447961DBDF42A7A87C 32D152B7FB553CA31D19F424EC4F5541640A63EA6EA4BBE2DF ; (----------------------------------------------------------------------------) @Primorial_13@ ( Regs : none ) .DF7F941F80ED1DE111AE899E83C533DCB51B5B3E9B93A9EB438F626BA00042CAA3 32D3B7C02A692EC7EFBEC2C71BCCFEE054C1AA85F5BE6F2335C632E7F7EFDA8A00 AC81AA04E378D0943C3B4715EBF66980379D08CE01CC9ACD117B548527C35D9BEA 35BFE478AF6BF28E82D99A460C05EFACF78141F2FF97499F83A2FDAED194AA74F8 E54DB2464810B5601E841DD1F66E573D29E77DFFBD738E33E8C83336691F4C3389 8359BF5FC93667D300FD745C70AE9398C7FA74ED8AA75FC3A983AA5050B572A075 49C564B940157B3CD97D2F933D78D7E5C7C90B9782EBE17EFAC8AA684C5F20C0D8 7D8380A0F702301B907E72EC1B1C7C6B3BAFE9D2EEDF5D4B23 ; (----------------------------------------------------------------------------) @Primorial_14@ ( Regs : none ) .000E54ACDDDF61FBC73D193DA8AA096A0B33B3EB7F534B759E0972F6E8B8BC4BA0 0CA24C0D6AC72D480747CC3AD0ABD7983554250D7B1054659BB84CD1D6F6FBE471 435DB764589BBFFCB0BCF65FC09297466872D03B879E29196D82D6C8F463D21B01 FC143049F9E5F9697822459613E4E2502F038E383D82D92AE29CC3E8CBA5D9938E 5124C738E9DA70834AEC01DA3C53E709BC3622EF08BCFC6E94FB22CA86D78B94A0 B9191DD394F13B8623F20C0FC0F8A0A086A1339C6AD69DE86BD7BB5D6455A08626 A40DD4E49A7A879D7B349FC314EBFDD7243A99106FDC7D4A2927E9EF1FE867F5CD E27C6EB4BA47B6DB9E47A65860E79946AACD9B68A68298E9B5 ; (----------------------------------------------------------------------------) @Primorial_15@ ( Regs : none ) .001057C207A1A28B767E36B63AA9C1C29B19BC31128BB880C170FA9CDDF1EC3B37 CDC6B07F99E450E3802843399C8560D67CE82836C386AF84861CBE8A5326831908 8C193D76506F031DF5E4788B533427900D5FCFE24D4F7E47D884B47F4EFA4690ED 47D2D310B3BB4B33F24949494414362E5CB74968141906C6FAA62C7460F9F57CA4 E1B8E85E5659ADA58E7DCA4D158BEBFCC49B8FB1B626BEAE18783F892D92CEDD78 A116104E353FB117A3C470BAF95E7190FDA6C1930859DAFD1F31BA5EE562BD366E 05014DE3887C3D1AA4B91E39451B2646AD4DEE062107EE09811EB1161B116AF1A2 A9397C8B9441E3D43022EB4438B2C4D647F58FFF07132A3983 ; (----------------------------------------------------------------------------) @Primorial_16@ ( Regs : none ) .00074781F780923D5B4A7E2D8DA1377F5693F9794EFA6356D2EC2B483BBF57ECDC 9F9A81E049D6AA12582F1315FA4510C91F77AC411DAFE911F3E5C29B2DF02902E2 8732AF6A6DD6C49C37FE1AC096E44DE8D8CA6DF6860A654DBC10E23406BC3AB683 C67A7C949261C087A5B08E242D8EC2DD9A227594A278BF71DB94B3ED87555AF554 199E526F9830D5D8728872B979B720ED6458C91E85E528CA63A522AE13058426F7 C458F5BE5EDE1D13BE37BFB599208EF1B93A679E177E9D8A4342AF93BCFF66D07A CBED7D77F69444C5C18FA5EDDF8394ED31622A6F5E4BA43ABBD91EE175C4395E87 C2CE450592A98DC1F99E2FBB1BEF75388195D26227026D3AEB ; (----------------------------------------------------------------------------) @Primorial_17@ ( Regs : none ) .000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000028C5ED2EF4D38F6C460E1CF82D ; (----------------------------------------------------------------------------) ( Number of 'passing' M-R shots required before we will say that a candidate integer is a 'probable prime': 32. Can change this if you dare. ) @MR-Shots@ ( Regs : none ) .20 ; (----------------------------------------------------------------------------) ( Bitmask imposed, via logical OR, on the randomly-generated candidates. Consists of a 1 in the uppermost position for the current FZ width, and a 1 in the lowermost position, to give ODD integers of desired width. ) @Candidate-Bitmask@ ( Regs : none ) .1 .0 ~ W .1 - LS .1 | ; (----------------------------------------------------------------------------) ( Take an integer N and a Primorial P from stack. N MUST BE > 1; assumed to be true, given that the Candidate Bitmask is > 1. if N is Relatively Prime vs. Primorial: Return 0; else: return 1. ) @P-Litmus@ ( Regs : none ) ( N and P are on the stack already. Now find GCD(N, P) : ) G ( Was the GCD equal to 1 ? ) .1 = ( Invert the answer; i.e. a 'fail' will result in 1, a 'pass' -- 0 : ) .1 ^ ; (----------------------------------------------------------------------------) ( Take a Bitmask specifying the bits that must be set to 1, from the stack. Generate RANDOM integers, until obtains one that, when OR'd with Bitmask, passes the Primorial Litmus. ) @Make-Candidate@ ( Regs : u, m, z ) ( Get the Bitmask from the stack, and assign to m : ) $m ( Begin a loop: ) : ( u := u + 1 , i.e. increment the 'RNG shots' counter: ) u .1 + $u ( Generate a random FZ of the current FZ width : ) ? ( Take the mandatory-ones Bitmask, and OR it into the random FZ from above, then store this to z: ) m | $z ( Run z through the Primorial Litmus: ) @Primorial_01! z @P-Litmus! ( Comment out below to vary the # of primorial sections : ) ( If 'passed', then the next: ) { .1 }{ @Primorial_02! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_03! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_04! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_05! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_06! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_07! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_08! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_09! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_10! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_11! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_12! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_13! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_14! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_15! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_16! z @P-Litmus! }_ ( If 'passed', then the next: ) { .1 }{ @Primorial_17! z @P-Litmus! }_ ( If 1, i.e. Litmus failed, cycle the loop; otherwise we're done: ) , ( Return the z which passed the Primorial Litmus: ) z ; (----------------------------------------------------------------------------) ( Take integers N and I from stack (I is on the top of stack, followed by N) ; Fire up to I shots of Miller-Rabin Test on N, each with a RANDOM witness; If ALL I shots PASSED, i.e. M-R did NOT 'find composite' in any of them : Return 0; else (i.e. if any shot FAILED) : Return 1 IMMEDIATELY. ) @Iterated-MR-Test@ ( Regs : i, n, r ) ( i := Maximum number of Miller-Rabin shots that we will perform : ) $i ( n := N, i.e. store a copy of N: ) $n ( Begin a loop: ) : ( Put n on the stack: ) n ( Generate a random Witness for this shot: ) ? ( Recall that it will always be brought into the valid range, automatically, in constant time. See also Ch. 16A. ) ( Increment RNG-for-Witness counter : ) w .1 + $w ( Run a M-R test; outputs 1 if FOUND composite, and 0 if NOT: ) P ( r := result ) $r ( i := i - 1 , i.e. decrement the shots counter: ) i .1 - $i ( If any shots still remain... ) i .0 > ( Invert the M-R result: if 'NOT found composite', give a 1 : ) r .1 ^ ( ...shots remain, AND current one did not 'find composite' : ) & ( ... then have a 1, and we cycle the loop, for the next shot; Otherwise, we're done: ) , ( At this point, N has failed a M-R shot, or passed all of the shots; In either case, we return r, which will be 0 IFF all shots passed, and otherwise 1 : ) r ; (----------------------------------------------------------------------------) @Initialize@ ( Regs: u, w, t, k ) ( Initialize u, 'RNG' counter, i.e. how many random FZ used for candidates : ) .0 $u ( Initialize w, counter of RNG invocations for use as M-R Witnesses : ) .0 $w ( Initialize t, 'tries' counter, i.e. how many GCD-filtered candidates tried: ) .0 $t ( Initialize k to the Bitmask that is to be imposed on candidates : ) @Candidate-Bitmask! $k ; (----------------------------------------------------------------------------) @Make-Probable-Prime@ ( Regs: t, k, x ) ( Begin the prime generation loop: ) : ( t := t + 1 , i.e. increment the 'tries' counter: ) t .1 + $t ( Get a candidate x, using Bitmask k, which passes Primorial Litmus: ) k @Make-Candidate! $x ( Perform MR-Shots of the Miller-Rabin Test: ) x @MR-Shots! @Iterated-MR-Test! ( If not yet found a candidate which passed both the initial Primorial Litmus and then the full number of M-R shots, then cycle the loop : ) , ( At this point, we have found a 'probable prime' candidate, and will print: ) ( ... finally, the candidate which passed all of the requested tests : ) [Probable Prime Integer : ] x # ; (----------------------------------------------------------------------------) @Print-Params@ ( Regs: k ) ( ... the Bitmask used : ) [Bitmask Imposed on Candidates : ] k # ( ... the number of 'passing' M-R shots required for termination : ) [Number of Mandated M-R Shots : ] @MR-Shots! # ; (----------------------------------------------------------------------------) @Print-Stats@ ( Regs: u, w, t ) ( ... the 'RNG shots' counter : ) [Number of Random FZ Candidates : ] u # ( ... the 'RNG witness' counter : ) [Number of Random FZ as Witness : ] w # ( ... the RNG total use counter : ) [Total of Random FZ Invocations : ] u w + # ( ... the 'tries' counter, i.e. how many passed Primorial Litmus : ) [GCD-Filtered Candidates Tested : ] t # ; (------------------------------ Main Program : ------------------------------) ( Initialize params and stats counters : ) @Initialize! ( Print Params : ) @Print-Params! [ ] ( q := # of primes to generate : ) @Number-of-Primes! $q ( Begin the main loop: ) : ( q := q - 1 , i.e. decrement the primes counter: ) q .1 - $q ( Generate a probable prime : ) @Make-Probable-Prime! ( If shots remain, cycle the loop : ) q , [ Stats: ] @Print-Stats! ( Now, terminate with a 'Yes' Verdict, as we have succeeded : ) QY (--------------------------------~~The End~~---------------------------------)