zrandom.c

Calc Software Package for Number Calc

 *		  r = pmod(last_r, 2, n);
 *	      } while (r > last_r);	(* r is the new quadratic residue *)
 *	  } else {
 *	      quit "newn (2nd arg) must be 3 mod 4";
 *	  }
 *
 *    seed < 0, newn >= 2^32:
 *    -----------------------
 *	Reserved for future use.
 *
 *    any seed, 20 < newn < 1007:
 *    ---------------------------
 *	Reserved for future use.
 *
 *    seed >= 2^32, 0 < newn <= 20:
 *    -----------------------------
 *	Set the Blum modulus to one of the the pre-defined Blum moduli.
 *	See below for the values of these pre-defined Blum moduli and how
 *	they were computed.
 *
 *	We will use the seed arg to compute a new quadratic residue.
 *	We will successively square it mod Blum modulus until we get
 *	a smaller value (modulus wrap).
 *
 *	The follow calc resource file produces an equivalent effect:
 *
 *	  n = n[newn];		(* n is new Blum modulus, see below *)
 *	  r = seed;
 *	  do {
 *	      last_r = r;
 *	      r = pmod(last_r, 2, n);
 *	  } while (r > last_r); (* r is the new quadratic residue *)
 *
 *    0 < seed < 2^32, 0 < newn <= 20:
 *    --------------------------------
 *	Reserved for future use.
 *
 *    seed == 0, 0 < newn <= 20:
 *    --------------------------
 *	Set the Blum modulus to one of the the pre-defined Blum moduli.
 *	The new quadratic residue will also be set to one of
 *	the pre-defined quadratic residues.
 *
 *	The follow calc resource file produces an equivalent effect:
 *
 *	  srandom(r[newn], n[newn])
 *
 *	or in other words:
 *
 *	  n = n[newn];		(* n is the new Blum modulus, see below *)
 *	  r = r[newn];		(* r is the new quadratic residue *)
 *
 *	The pre-defined Blum moduli was computed by searching for Blum
 *	primes (primes == 3 mod 4) starting from new values that
 *	were selected by LavaRnd, a hardware random number generator.
 *	See the URL:
 *
 *	    http://www.LavaRnd.org/
 *
 *	for an explination of how the LavaRnd random number generator works.
 *
 *	For a given newn, we select a given bit length.	 For 0 < newn <= 20,
 *	the bit length selected was by:
 *
 *	    bitlen = 2^(int((newn-1)/4)+7) + small_random_value;
 *
 *	where small_random_value is also generated by LavaRnd.	 For
 *	1 <= newn <= 16, small_random_value is a random value in [0,40).
 *	For 17 < newn <= 20, small_random_value is a random value in [0,120).
 *	Given two random integers generated by LavaRnd, we used the following
 *	to compute Blum primes:
 *
 *	  (* find the first Blum prime *)
 *	  fp = int((ip-1)/2);		(* ip was generated by LavaRnd *)
 *	  do {
 *	      fp = nextcand(fp+2, 25, 0, 3, 4);
 *	      p = 2*fp+1;
 *	  } while (ptest(p, 25) == 0);
 *
 *	  (* find the 2nd Blum prime *)
 *	  fq = int((iq-1)/2);		(* iq was generated by LavaRnd *)
 *	  do {
 *	      fq = nextcand(fq+2, 25, 0, 3, 4);
 *	      q = 2*fq+1;
 *	  } while (ptest(q, 25) == 0);
 *
 *	  (* compute the Blum modulus *)
 *	  n[newn] = p * q;
 *
 *	The pre-defined quadratic residues was also generated by LavaRnd.
 *	The value produced by LavaRnd was squared mod the Blum moduli
 *	that was previously computed.
 *
 *	The purpose of these pre-defined Blum moduli is to provide users with
 *	an easy way to use a generator where the individual Blum primes used
 *	are not well known.  True, these values are in some way "MAGIC", on
 *	the other hand that is their purpose!  If this bothers you, don't
 *	use them.  See the section "FOR THE PARANOID" below for details.
 *
 *	The value 'newn' determines which pre-defined generator is used.
 *	For a given 'newn' the Blum modulus 'n[newn]' (product of 2 Blum
 *	(primes) and new quadratic residue 'r[newn]' is set as follows:
 *
 *	newn ==	 1: (Blum modulus bit length 130)
 *	n[ 1] = 0x5049440736fe328caf0db722d83de9361
 *	r[ 1] = 0xb226980f11d952e74e5dbb01a4cc42ec
 *
 *	newn ==	 2: (Blum modulus bit length 137)
 *	n[ 2] = 0x2c5348a2555dd374a18eb286ea9353443f1
 *	r[ 2] = 0x40f3d643446cd710e3e893616b21e3a218
 *
 *	newn ==	 3: (Blum modulus bit length 147)
 *	n[ 3] = 0x9cfd959d6ce4e3a81f1e0f2ca661f11d001f1
 *	r[ 3] = 0xfae5b44d9b64ff5cea4f3e142de2a0d7d76a
 *
 *	newn ==	 4: (Blum modulus bit length 157)
 *	n[ 4] = 0x3070f9245c894ed75df12a1a2decc680dfcc0751
 *	r[ 4] = 0x20c2d8131b2bdca2c0af8aa220ddba4b984570
 *
 *	newn ==	 5: (Blum modulus bit length 257)
 *	n[ 5] = 0x2109b1822db81a85b38f75aac680bc2fa5d3fe1118769a0108b99e5e799
 *		166ef1
 *	r[ 5] = 0x5e9b890eae33b792e821a9605f5df6db234f7b7d1e70aeed0e6c77c859e
 *		2efa9
 *
 *	newn ==	 6: (Blum modulus bit length 259)
 *	n[ 6] = 0xa7bfd9d7d9ada2c79f2dbf2185c6440263a38db775ee732dad85557f1e1
 *		ddf431
 *	r[ 6] = 0x5e94a02f88667154e097aedece1c925ce1f3495d2c98eccfc5dc2e80c94
 *		04daf
 *
 *	newn ==	 7: (Blum modulus bit length 286)
 *	n[ 7] = 0x43d87de8f2399ef237801cd5628643fcff569d6b0dcf53ce52882e7f602
 *		f9125cf9ec751
 *	r[ 7] = 0x13522d1ee014c7bfbe90767acced049d876aefcf18d4dd64f0b58c3992d
 *		2e5098d25e6
 *
 *	newn ==	 8: (Blum modulus bit length 294)
 *	n[ 8] = 0x5847126ca7eb4699b7f13c9ce7bdc91fed5bdbd2f99ad4a6c2b59cd9f0b
 *		c42e66a26742f11
 *	r[ 8] = 0x853016dca3269116b7e661fa3d344f9a28e9c9475597b4b8a35da929aae
 *		95f3a489dc674
 *
 *	newn ==	 9: (Blum modulus bit length 533)
 *	n[ 9] = 0x39e8be52322fd3218d923814e81b003d267bb0562157a3c1797b4f4a867
 *		52a84d895c3e08eb61c36a6ff096061c6fd0fdece0d62b16b66b980f95112
 *		745db4ab27e3d1
 *	r[ 9] = 0xb458f8ad1e6bbab915bfc01508864b787343bc42a8aa82d9d2880107e3f
 *		d8357c0bd02de3222796b2545e5ab7d81309a89baedaa5d9e8e59f959601e
 *		f2b87d4ed20d
 *
 *	newn == 10: (Blum modulus bit length 537)
 *	n[10] = 0x25f2435c9055666c23ef596882d7f98bd1448bf23b50e88250d3cc952c8
 *		1b3ba524a02fd38582de74511c4008d4957302abe36c6092ce222ef9c73cc
 *		3cdc363b7e64b89
 *	r[10] = 0x66bb7e47b20e0c18401468787e2b707ca81ec9250df8cfc24b5ffbaaf2c
 *		f3008ed8b408d075d56f62c669fadc4f1751baf950d145f40ce23442aee59
 *		4f5ad494cfc482
 *
 *	newn == 11: (Blum modulus bit length 542)
 *	n[11] = 0x497864de82bdb3094217d56b874ecd7769a791ea5ec5446757f3f9b6286
 *		e58704499daa2dd37a74925873cfa68f27533920ee1a9a729cf522014dab2
 *		2e1a530c546ee069
 *	r[11] = 0x8684881cb5e630264a4465ae3af8b69ce3163f806549a7732339eea2c54
 *		d5c590f47fbcedfa07c1ef5628134d918fee5333fed9c094d65461d88b13a
 *		0aded356e38b04
 *
 *	newn == 12: (Blum modulus bit length 549)
 *	n[12] = 0x3457582ab3c0ccb15f08b8911665b18ca92bb7c2a12b4a1a66ee4251da1
 *		90b15934c94e315a1bf41e048c7c7ce812fdd25d653416557d3f09887efad
 *		2b7f66d151f14c7b99
 *	r[12] = 0xdf719bd1f648ed935870babd55490137758ca3b20add520da4c5e8cdcbf
 *		c4333a13f72a10b604eb7eeb07c573dd2c0208e736fe56ed081aa9488fbc4
 *		5227dd68e207b4a0
 *
 *	newn == 13: (Blum modulus bit length 1048)
 *	n[13] = 0x1517c19166b7dd21b5af734ed03d833daf66d82959a553563f4345bd439
 *		510a7bda8ee0cb6bf6a94286bfd66e49e25678c1ee99ceec891da8b18e843
 *		7575113aaf83c638c07137fdd3a76c3a49322a11b5a1a84c32d99cbb2b056
 *		671589917ed14cc7f1b5915f6495dd1892b4ed7417d79a63cc8aaa503a208
 *		e3420cca200323314fc49
 *	r[13] = 0xd42e8e9a560d1263fa648b04f6a69b706d2bc4918c3317ddd162cb4be7a
 *		5e3bbdd1564a4aadae9fd9f00548f730d5a68dc146f05216fe509f0b8f404
 *		902692de080bbeda0a11f445ff063935ce78a67445eae5c9cea5a8f6b9883
 *		faeda1bbe5f1ad3ef6409600e2f67b92ed007aba432b567cc26cf3e965e20
 *		722407bfe46b7736f5
 *
 *	newn == 14: (Blum modulus bit length 1054)
 *	n[14] = 0x5e56a00e93c6f4e87479ac07b9d983d01f564618b314b4bfec7931eee85
 *		eb909179161e23e78d32110560b22956b22f3bc7e4a034b0586e463fd40c6
 *		f01a33e30ede912acb86a0c1e03483c45f289a271d14bd52792d0a076fdfe
 *		fe32159054b217092237f0767434b3db112fee83005b33f925bacb3185cc4
 *		409a1abdef8c0fc116af01
 *	r[14] = 0xf7aa7cb67335096ef0c5d09b18f15415b9a564b609913f75f627fc6b0c5
 *		b686c86563fe86134c5a0ea19d243350dfc6b9936ba1512abafb81a0a6856
 *		c9ae7816bf2073c0fb58d8138352b261a704b3ce64d69dee6339010186b98
 *		3677c84167d4973444194649ad6d71f8fa8f1f1c313edfbbbb6b1b220913c
 *		c8ea47a4db680ff9f190
 *
 *	newn == 15: (Blum modulus bit length 1055)
 *	n[15] = 0x97dd840b9edfbcdb02c46c175ba81ca845352ebe470be6075326a26770c
 *		ab84bfc0f2e82aa95aac14f40de42a0590445b902c2b8ebb916753e72ab86
 *		c3278cccc1a783b3e962d81b80df03e4380a8fa08b0d86ed0caa515c196a5
 *		30e49c558ddb53082310b1d0c7aee6f92b619798624ffe6c337299bc51ff5
 *		d2c721061e7597c8d97079
 *	r[15] = 0xb8220703b8c75869ab99f9b50025daa8d77ca6df8cef423ede521f55b1c
 *		25d74fbf6d6cc31f5ef45e3b29660ef43797f226860a4aa1023dbe522b1fe
 *		6224d01eb77dee9ad97e8970e4a9e28e7391a6a70557fa0e46eca78866241
 *		ba3c126fc0c5469f8a2f65c33db95d1749d3f0381f401b9201e6abd43d98d
 *		b92e808f0aaa6c3e2110
 *
 *	newn == 16: (Blum modulus bit length 1062)
 *	n[16] = 0x456e348549b82fbb12b56f84c39f544cb89e43536ae8b2b497d426512c7
 *		f3c9cc2311e0503928284391959e379587bc173e6bc51ba51c856ba557fee
 *		8dd69cee4bd40845bd34691046534d967e40fe15b6d7cf61e30e283c05be9
 *		93c44b6a2ea8ade0f5578bd3f618336d9731fed1f1c5996a5828d4ca857ac
 *		2dc9bd36184183f6d84346e1
 *	r[16] = 0xb0d7dcb19fb27a07973e921a4a4b6dcd7895ae8fced828de8a81a3dbf25
 *		24def719225404bfd4977a1508c4bac0f3bc356e9d83b9404b5bf86f6d19f
 *		f75645dffc9c5cc153a41772670a5e1ae87a9521416e117a0c0d415fb15d2
 *		454809bad45d6972f1ab367137e55ad0560d29ada9a2bcda8f4a70fbe04a1
 *		abe4a570605db87b4e8830
 *
 *	newn == 17: (Blum modulus bit length 2062)
 *	n[17] = 0x6177813aeac0ffa3040b33be3c0f96e0faf97ca54266bfedd7be68494f7
 *		6a7a91144598bf28b3a5a9dc35a6c9f58d0e5fb19839814bc9d456bff7f29
 *		953bdac7cafd66e2fc30531b8d544d2720b97025e22b1c71fa0b2eb9a499d
 *		49484615d07af7a3c23b568531e9b8507543362027ec5ebe0209b4647b7ff
 *		54be530e9ef50aa819c8ff11f6d7d0a00b25e88f2e6e9de4a7747022b949a
 *		b2c2e1ab0876e2f1177105718c60196f6c3ac0bde26e6cd4e5b8a20e9f0f6
 *		0974f0b3868ff772ab2ceaf77f328d7244c9ad30e11a2700a120a314aff74
 *		c7f14396e2a39cc14a9fa6922ca0fce40304166b249b574ffd9cbb927f766
 *		c9b150e970a8d1edc24ebf72b72051
 *	r[17] = 0x53720b6eaf3bc3b8adf1dd665324c2d2fc5b2a62f32920c4e167537284d
 *		a802fc106be4b0399caf97519486f31e0fa45a3a677c6cb265c5551ba4a51
 *		68a7ce3c29731a4e9345eac052ee1b84b7b3a82f906a67aaf7b35949fd7fc
 *		2f9f4fbc8c18689694c8d30810fff31ebee99b1cf029a33bd736750e7fe0a
 *		56f7e1d2a9b5321b5117fe9a10e46bf43c896e4a33faebd584f7431e7edbe
 *		bd1703ccee5771b44f0c149888af1a4264cb9cf2e0294ea7719ed6fda1b09
 *		fa6e016c039aeb6d02a03281bcea8c278dd2a807eacae6e52ade048f58f2e
 *		b5193f4ffb9dd68467bc6f8e9d14286bfef09b0aec414c9dadfbf5c46d945
 *		d147b52aa1e0cbd625800522b41dac
 *
 *	newn == 18: (Blum modulus bit length 2074)
 *	n[18] = 0x68f2a38fb61b42af07cb724fec0c7c65378efcbafb3514e268d7ee38e21
 *		a5680de03f4e63e1e52bde1218f689900be4e5407950539b9d28e9730e8e6
 *		ad6438008aa956b259cd965f3a9d02e1711e6b344b033de6425625b6346d2
 *		ca62e41605e8eae0a7e2f45c25119ef9eece4d3b18369e753419d94118d51
 *		803842f4de5956b8349e6a0a330145aa4cd1a72afd4ef9db5d8233068e691
 *		18ff4b93bcc67859f211886bb660033f8170640c6e3d61471c3b7dd62c595
 *		b156d77f317dc272d6b7e7f4fdc20ed82f172fe29776f3bddf697fb673c70
 *		defd6476198a408642ed62081447886a625812ac6576310f23036a7cd3c93
 *		1c96f7df128ad4ed841351b18c8b78629
 *	r[18] = 0x4735e921f1ac6c3f0d5cda84cd835d75358be8966b99ff5e5d36bdb4be1
 *		2c5e1df70ac249c0540a99113a8962778dc75dac65af9f3ab4672b4c575c4
 *		9926f7f3f306fd122ac033961d042c416c3aa43b13ef51b764d505bb1f369
 *		ac7340f8913ddd812e9e75e8fde8c98700e1d3353da18f255e7303db3bcbb
 *		eda4bc5b8d472fbc9697f952cfc243c6f32f3f1bb4541e73ca03f5109df80
 *		37219a06430e88a6e94be870f8d36dbcc381a1c449c357753a535aa5666db
 *		92af2aaf1f50a3ddde95024d9161548c263973665a909bd325441a3c18fc7
 *		0502f2c9a1c944adda164e84a8f3f0230ff2aef8304b5af333077e04920db
 *		a179158f6a2b3afb78df2ef9735ea3c63
 *
 *	newn == 19: (Blum modulus bit length 2133)
 *	n[19] = 0x230d7ab23bb9e8d6788b252ad6534bdde276540721c3152e410ad4244de
 *		b0df28f4a6de063ba1e51d7cd1736c3d8410e2516b4eb903b8d9206b92026
 *		64cacbd0425c516833770d118bd5011f3de57e8f607684088255bf7da7530
 *		56bf373715ed9a7ab85f698b965593fe2b674225fa0a02ebd87402ffb3d97
 *		172acadaa841664c361f7c11b2af47a472512ee815c970af831f95b737c34
 *		2508e4c23f3148f3cdf622744c1dcfb69a43fd535e55eebcdc992ee62f2b5
 *		2c94ac02e0921884fe275b3a528bdb14167b7dec3f3f390cd5a82d80c6c30
 *		6624cc7a7814fb567cd4d687eede573358f43adfcf1e32f4ee7a2dc4af029
 *		6435ade8099bf0001d4ae0c7d204df490239c12d6b659a79
 *	r[19] = 0x8f1725f21e245e4fc17982196605b999518b4e21f65126fa6fa759332c8
 *		e27d80158b7537da39d001cc62b83bbef0713b1e82f8293dad522993f86d1
 *		761015414b2900e74fa23f3eaaa55b31cffd2e801fefb0ac73fd99b5d0cf9
 *		a635c3f4c73d8892d36ad053fc17a423cdcbcf07967a8608c7735e287d784
 *		ae089b3ddea9f2d2bb5d43d2ee25be346832e8dd186fc7a88d82847c03d1c
 *		05ee52c1f2a51a85f733338547fdbab657cb64b43d44d41148eb32ea68c7e
 *		66a8d47806f460cd6573b6ca1dd3eeaf1ce8db9621f1e121d2bb4a1878621
 *		dd2dbdd7b5390ab06a5dcd9307d6662eb4248dff2ee263ef2ab778e77724a
 *		14c62406967daa0d9ad4445064483193d53a5b7698ef473
 *
 *	newn == 20: (Blum modulus bit length 2166)
 *	n[20] = 0x4fd2b820e0d8b13322e890dddc63a0267e5b3a648b03276066a3f356d79
 *		660c67704c1be6803b8e7590ee8a962c8331a05778d010e9ba10804d661f3
 *		354be1932f90babb741bd4302a07a92c42253fd4921864729fb0f0b1e0a42
 *		d66b6777893195abd2ee2141925624bf71ad7328360135c565064ee502773
 *		6f42a78b988f47407ba4f7996892ffdc5cf9e7ab78ac95734dbf4e3a3def1
 *		615b5b4341cfbf6c3d0a61b75f4974080bbac03ee9de55221302b40da0c50
 *		ded31d28a2f04921a532b3a486ae36e0bb5273e811d119adf90299a74e623
 *		3ccce7069676db00a3e8ce255a82fd9748b26546b98c8f4430a8db2a4b230
 *		fa365c51e0985801abba4bbcf3727f7c8765cc914d262fcec3c1d081
 *	r[20] = 0x46ef0184445feaa3099293ee960da14b0f8b046fa9f608241bc08ddeef1
 *		7ee49194fd9bb2c302840e8da88c4e88df810ce387cc544209ec67656bd1d
 *		a1e9920c7b1aad69448bb58455c9ae4e9cd926911b30d6b5843ff3d306d56
 *		54a41dc20e2de4eb174ec5ac3e6e70849de5d5f9166961207e2d8b31014cf
 *		35f801de8372881ae1ba79e58942e5bef0a7e40f46387bf775c54b1d15a14
 *		40e84beb39cd9e931f5638234ea730ed81d6fca1d7cea9e8ffb171f6ca228
 *		56264a36a2a783fd7ac39361a6598ed3a565d58acf1f5759bd294e5f53131
 *		bc8e4ee3750794df727b29b1f5788ae14e6a1d1a5b26c2947ed46f49e8377
 *		3292d7dd5650580faebf85fd126ac98d98f47cf895abdc7ba048bd1a
 *
 *	NOTE: The Blum moduli associated with 1 <= newn < 9 are subject