Main Page   Modules   Data Structures   File List   Data Fields   Globals   Related Pages  

beecrypt/mp32prime.c

Go to the documentation of this file.
00001 
00007 /*
00008  * Copyright (c) 2000, 2001 Virtual Unlimited B.V.
00009  *
00010  * Author: Bob Deblier <bob@virtualunlimited.com>
00011  *
00012  * This library is free software; you can redistribute it and/or
00013  * modify it under the terms of the GNU Lesser General Public
00014  * License as published by the Free Software Foundation; either
00015  * version 2.1 of the License, or (at your option) any later version.
00016  *
00017  * This library is distributed in the hope that it will be useful,
00018  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00019  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00020  * Lesser General Public License for more details.
00021  *
00022  * You should have received a copy of the GNU Lesser General Public
00023  * License along with this library; if not, write to the Free Software
00024  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00025  *
00026  */
00027 
00028 #include "system.h"
00029 #include "mp32prime.h"
00030 #include "mp32.h"
00031 #include "mp32barrett.h"
00032 #include "debug.h"
00033 
00052 /*@observer@*/ /*@unchecked@*/
00053 static uint32 spp_01[] =        /* primes 3 to 29 */
00054 { 0xc0cfd797 };
00055 
00058 /*@observer@*/ /*@unchecked@*/
00059 static uint32 spp_02[] =        /* primes 3 to 53 */
00060 { 0xe221f97c, 0x30e94e1d };
00061 
00064 /*@observer@*/ /*@unchecked@*/
00065 static uint32 spp_03[] =        /* primes 3 to 73 */
00066 { 0x41cd66ac, 0xc237b226, 0x81a18067 };
00067 
00070 /*@observer@*/ /*@unchecked@*/
00071 static uint32 spp_04[] =        /* primes 3 to 101 */
00072 { 0x5797d47c, 0x51681549, 0xd734e4fc, 0x4c3eaf7f };
00073 
00076 /*@observer@*/ /*@unchecked@*/
00077 static uint32 spp_05[] =        /* primes 3 to 113 */
00078 { 0x02c4b8d0, 0xd2e0d937, 0x3935200f, 0xb49be231,
00079   0x5ce1a307 };
00080 
00083 /*@observer@*/ /*@unchecked@*/
00084 static uint32 spp_06[] =        /* primes 3 to 149 */
00085 { 0x1e6d8e2a, 0x0ffceafb, 0xbcbfc14a, 0x4c3bc1e1,
00086   0x009c6a22, 0xa0a7adf5 };
00087 
00090 /*@observer@*/ /*@unchecked@*/
00091 static uint32 spp_07[] =        /* primes 3 to 167 */
00092 { 0x049265d3, 0x574cefd0, 0x4229bfd6, 0x62a4a46f,
00093   0x8611ed02, 0x26c655f0, 0x76ebade3 };
00094 
00097 /*@observer@*/ /*@unchecked@*/
00098 static uint32 spp_08[] =        /* primes 3 to 193 */
00099 { 0xdbf05b6f, 0x5654b3c0, 0xf5243551, 0x43958688,
00100   0x9f155887, 0x819aed2a, 0xc05b9335, 0x2be98677 };
00101 
00104 /*@observer@*/ /*@unchecked@*/
00105 static uint32 spp_09[] =        /* primes 3 to 223 */
00106 { 0x5e75cec8, 0xb5de5ea1, 0x5da8302a, 0x2f28b4ad,
00107   0x2735bdc3, 0x9344c52e, 0x67570925, 0x6feb71ef,
00108   0x6811d741 };
00109 
00112 /*@observer@*/ /*@unchecked@*/
00113 static uint32 spp_10[] =        /* primes 3 to 239 */
00114 { 0x3faa5dad, 0xb695ce58, 0x4a579328, 0xeab20f1f,
00115   0xef00fe27, 0xffc36456, 0x0a65723e, 0x27d8884a,
00116   0xd59da0a9, 0x92f77529 };
00117 
00120 /*@observer@*/ /*@unchecked@*/
00121 static uint32 spp_11[] =        /* primes 3 to 263 */
00122 { 0x3c9b6e49, 0xb7cf685b, 0xe7f3a239, 0xfb4084cb,
00123   0x166885e3, 0x9d4f65b4, 0x0bb0e51c, 0x0a5d36fe,
00124   0x98c32069, 0xfd5c441c, 0x6d82f115 };
00125 
00128 /*@observer@*/ /*@unchecked@*/
00129 static uint32 spp_12[] =        /* primes 3 to 281 */
00130 { 0x501201cc, 0x51a492a5, 0x44d3900a, 0xd4f8b32a,
00131   0x203c8584, 0x06a4457c, 0xab0b4f80, 0x5ab18ac6,
00132   0xeb9572ac, 0x6e9394fa, 0x522bffb6, 0xf44af2f3 };
00133 
00136 /*@observer@*/ /*@unchecked@*/
00137 static uint32 spp_13[] =        /* primes 3 to 311 */
00138 { 0x9397b5b4, 0x414dc331, 0x04561364, 0x79958cc8,
00139   0xfd5ea01f, 0x5d5e9f61, 0xbd0f1cb6, 0x24af7e6a,
00140   0x3284dbb2, 0x9857622b, 0x8be980a6, 0x5456a5c1,
00141   0xed928009 };
00142 
00145 /*@observer@*/ /*@unchecked@*/
00146 static uint32 spp_14[] =        /* primes 3 to 331 */
00147 { 0x0120eb4d, 0x70279230, 0x9ed122fc, 0xe0488be4,
00148   0x1d0c99f5, 0xd8c039ad, 0x058c90b4, 0x780500fe,
00149   0xf39c05cc, 0x09817a27, 0xc3e1776a, 0x246b6af2,
00150   0x946a10d6, 0x6eafaedf };
00151 
00154 /*@observer@*/ /*@unchecked@*/
00155 static uint32 spp_15[] =        /* primes 3 to 353 */
00156 { 0x03c91dd1, 0x2e893191, 0x94095649, 0x874b41d6,
00157   0x05810c06, 0x195d70eb, 0xbd54a862, 0x50c52733,
00158   0x06dc6648, 0x1c251ca4, 0xa02c9a04, 0x78c96f0d,
00159   0x02f0db0b, 0x39d624ca, 0x0b0441c1 };
00160 
00163 /*@observer@*/ /*@unchecked@*/
00164 static uint32 spp_16[] =        /* primes 3 to 379 */
00165 { 0x106aa9fb, 0x7646fa6e, 0xb0813c28, 0xc5d5f09f,
00166   0x077ec3ba, 0x238bfb99, 0xc1b631a2, 0x03e81187,
00167   0x233db117, 0xcbc38405, 0x6ef04659, 0xa4a11de4,
00168   0x9f7ecb29, 0xbada8f98, 0x0decece9, 0x2e30c48f };
00169 
00172 /*@observer@*/ /*@unchecked@*/
00173 static uint32 spp_17[] =        /* primes 3 to 401 */
00174 { 0x5aa88d8c, 0x594bb372, 0xc4bc813f, 0x4a87a266,
00175   0x1f984840, 0xdab15692, 0x2c2a177d, 0x95843665,
00176   0x6f36d41a, 0x11c35ccc, 0x2904b7e9, 0xc424eb61,
00177   0x3b3536a4, 0x0b2745bd, 0xadf1a6c9, 0x7b23e85a,
00178   0xdc6695c1 };
00179 
00182 /*@observer@*/ /*@unchecked@*/
00183 static uint32 spp_18[] =        /* primes 3 to 421 */
00184 { 0x0185dbeb, 0x2b8b11d3, 0x7633e9dc, 0x1eec5415,
00185   0x65c6ce84, 0x31d227ee, 0x28f0328a, 0x60c90118,
00186   0xae031cc5, 0xa781c824, 0xd1f16d25, 0xf4f0cccf,
00187   0xf35e9745, 0x79072ec8, 0xcaf1ac8e, 0xefd5566f,
00188   0xa15fb94f, 0xe34f5d37 };
00189 
00192 /*@observer@*/ /*@unchecked@*/
00193 static uint32 spp_19[] =        /* primes 3 to 443 */
00194 { 0x0cde6fd1, 0xcf108066, 0xcc548df9, 0x070e102c,
00195   0x2c651b88, 0x5f24f503, 0xaaffe276, 0xfeb57311,
00196   0x0c1e4592, 0xa35890d7, 0x678aaeee, 0x9f44800f,
00197   0xc43f999d, 0x5d06b89f, 0xcb22e533, 0x5a9287bc,
00198   0x6d75a3e9, 0x1e53906d, 0x413163d5 };
00199 
00202 /*@observer@*/ /*@unchecked@*/
00203 static uint32 spp_20[] =        /* primes 3 to 463 */
00204 { 0x833a505c, 0xf9922bee, 0xc80265a6, 0xd50e1cce,
00205   0xa22f6fec, 0x2eb84450, 0xcec64a3c, 0x0e10d472,
00206   0xdd653b9b, 0x51d81d0e, 0x3a3142ea, 0x49b91e3a,
00207   0x5e210232, 0x67bda426, 0x738730cf, 0xb8e6e2ae,
00208   0xc08c9d4b, 0xd2420066, 0xdccf95ef, 0x49a560b7 };
00209 
00212 /*@observer@*/ /*@unchecked@*/
00213 static uint32 spp_21[] =        /* primes 3 to 487 */
00214 { 0x035417f1, 0xe321c06c, 0xbe32ffce, 0xae752cc9,
00215   0xa9fe11a6, 0x3d94c946, 0x456edd7d, 0x5a060de1,
00216   0x84a826a6, 0xf0740c13, 0x48fa1038, 0x911d771d,
00217   0xb3773e87, 0x52300c29, 0xc82c3012, 0x131673bb,
00218   0x491cbd61, 0x55e565af, 0x4a9f4331, 0x0adbb0d7,
00219   0x06e86f6d };
00220 
00223 /*@observer@*/ /*@unchecked@*/
00224 static uint32 spp_22[] =        /* primes 3 to 509 */
00225 { 0x309d024b, 0xd5380319, 0x2ca33469, 0x0bafb43a,
00226   0x0abd5840, 0xfbeb24d1, 0xf49b6330, 0x47902bae,
00227   0x581ca4cb, 0xa778fdb1, 0x6dc0a6af, 0xef960687,
00228   0x16855d95, 0x93746604, 0x201f1919, 0xb725fcb7,
00229   0x8ffd0db8, 0xe8fa61a1, 0x6e1c0970, 0xbeb81adc,
00230   0xf49c82df, 0xf960d36f };
00231 
00234 /*@observer@*/ /*@unchecked@*/
00235 static uint32 spp_23[] =        /* primes 3 to 541 */
00236 { 0x01ab244a, 0x33bc047e, 0x804590b4, 0xc3207237,
00237   0xea503fa0, 0x7541b251, 0x57cfd03f, 0xf602c9d0,
00238   0x3dcd12ba, 0xa4947ae6, 0xc6ee61be, 0xedf6c716,
00239   0xfa45377d, 0x5b3c84fa, 0x5fb78b41, 0x395251eb,
00240   0xb6a5129c, 0x7699fb5c, 0xccec6d45, 0x56c9b8ea,
00241   0xfa05897c, 0xb8c5cf72, 0xb77603d9 };
00242 
00245 /*@observer@*/ /*@unchecked@*/
00246 static uint32 spp_24[] =        /* primes 3 to 569 */
00247 { 0x25eac89f, 0x8d4da338, 0x337b4985, 0x0d2d1489,
00248   0x2663177b, 0x4010af3d, 0xd23eeb0b, 0x228f3832,
00249   0xffcee2e5, 0xcbd1acc9, 0x8f47f251, 0x873380ae,
00250   0x10f0ffdd, 0x8e602ffa, 0x210f41f6, 0x69a1570a,
00251   0x93c158c1, 0xa9a8227f, 0xf81a90c5, 0x630e9c44,
00252   0x845c755c, 0x7df35a7d, 0x430c679a, 0x11575655 };
00253 
00256 /*@observer@*/ /*@unchecked@*/
00257 static uint32 spp_25[] =        /* primes 3 to 587 */
00258 { 0x01b515a8, 0xdca3d6e4, 0x69090373, 0x84febfe8,
00259   0xf32e06cf, 0x9bde8c89, 0x6b3f992f, 0x2ff23508,
00260   0xe1c01024, 0x3b8ad0c4, 0xac54e7c7, 0x3f4081d8,
00261   0xe495d54d, 0x74ed01e8, 0x9dfcbdde, 0x1fe7e61a,
00262   0x839bd902, 0xf43bf273, 0x2441f0ae, 0xb4211c70,
00263   0x6b3faafc, 0x0f200b35, 0x7485ce4a, 0x2f08f148,
00264   0xcce6887d };
00265 
00268 /*@observer@*/ /*@unchecked@*/
00269 static uint32 spp_26[] =        /* primes 3 to 607 */
00270 { 0x3383219d, 0x26454f06, 0xe2789b7f, 0x9c3b940e,
00271   0x03be2105, 0x798e3ff7, 0x945bd325, 0x997bc262,
00272   0x025598f8, 0x8577748e, 0xc7155ff8, 0x8a1ff4c9,
00273   0x2ce95bd8, 0xb015101f, 0x19b73b14, 0x81627f9a,
00274   0x6f83da3a, 0x03259fbd, 0x41f92a6e, 0x85ac6efa,
00275   0xde195be8, 0x6e66ba89, 0xb0ab042d, 0x3276976c,
00276   0x3dbeb3d7, 0x413ea96d };
00277 
00280 /*@observer@*/ /*@unchecked@*/
00281 static uint32 spp_27[] =        /* primes 3 to 619 */
00282 { 0x02ced4b7, 0xf15179e8, 0x7fcba6da, 0x7b07a6f3,
00283   0xf9311218, 0xa7b88985, 0xac74b503, 0xbf745330,
00284   0x6d0a23f5, 0x27a1fa9a, 0xc2b85f1a, 0x26152470,
00285   0x6ac242f3, 0x518cc497, 0x09a23d74, 0xff28da52,
00286   0xe7bbf7f7, 0xa63c1c88, 0x6f684195, 0x65e472ce,
00287   0x80751585, 0xc70e20c2, 0x2d15d3fe, 0xc1b40c7f,
00288   0x8e25dd07, 0xdb09dd86, 0x791aa9e3 };
00289 
00292 /*@observer@*/ /*@unchecked@*/
00293 static uint32 spp_28[] =        /* primes 3 to 647 */
00294 { 0x6e026454, 0x60adbd18, 0xcd52ce1a, 0x1beab1c0,
00295   0x36e468e9, 0xf350d69b, 0x1d357d08, 0x3a59f778,
00296   0xc2cc262b, 0x4a29ce52, 0x509bcf97, 0x349ba2bf,
00297   0x22402d71, 0x6b32517e, 0x1941e18a, 0xce76cbd8,
00298   0x5809701e, 0x70eaef96, 0x9aac365c, 0x8a9fea5e,
00299   0xc74d951d, 0xb361f061, 0xc4d14f00, 0x0d806db4,
00300   0xcd939110, 0xc7cab492, 0x2f3ea4c4, 0x852ca469 };
00301 
00304 /*@observer@*/ /*@unchecked@*/
00305 static uint32 spp_29[] =        /* primes 3 to 661 */
00306 { 0x074921f7, 0x6a76cec3, 0xaeb05f74, 0x60b21f16,
00307   0x49dece2f, 0x21bb3ed9, 0xe4cb4ebc, 0x05d6f408,
00308   0xed3d408a, 0xdee16505, 0xdc657c6d, 0x93877982,
00309   0xf2d11ce6, 0xcb5b0bb0, 0x579b3189, 0xb339c2cc,
00310   0xcf81d846, 0xa9fbde0c, 0x723afbc7, 0x36655d41,
00311   0x0018d768, 0x21779cf3, 0x52642f1b, 0x2d17165d,
00312   0xc7001c45, 0x4a84a45d, 0x66007591, 0x27e85693,
00313   0x2288d0fb };
00314 
00317 /*@observer@*/ /*@unchecked@*/
00318 static uint32 spp_30[] =        /* primes 3 to 683 */
00319 { 0x00872313, 0x1f66758a, 0x414bbebb, 0x2f8670bf,
00320   0x01dc959d, 0x74468901, 0x57c57f40, 0xe210c9c2,
00321   0x74f54469, 0x7c71cc1d, 0xe2be67a2, 0x03d8d56f,
00322   0x6c363fca, 0x0a78676a, 0x2b977789, 0x6ea2db50,
00323   0xdb31b737, 0x51992f73, 0x0def293e, 0xbc028877,
00324   0xdf95ac1b, 0x4d0c0128, 0x9a0b05e0, 0x0e6c0bc8,
00325   0xe61b766e, 0xc0943254, 0x1cd70f0f, 0xd5a0ce6b,
00326   0x8ab998fb, 0x8ab36e0d };
00327 
00330 /*@observer@*/ /*@unchecked@*/
00331 static uint32 spp_31[] =        /* primes 3 to 719 */
00332 { 0x1e595df4, 0x3064a8c9, 0xd61ae17b, 0xde1938f0,
00333   0x22ee6357, 0x35f4cadd, 0x3d39f473, 0xafed7df5,
00334   0x92ae0fd3, 0xfe910508, 0x9ad9e939, 0x988b0227,
00335   0x60dec749, 0xae7ee54f, 0xeb0572ac, 0x0aed266d,
00336   0x92daafd8, 0x6135f7a3, 0xe4e8bf05, 0x0124c928,
00337   0xb0d719d5, 0x2181aec8, 0x0f79820f, 0xcb158642,
00338   0x20969ec0, 0x1a480d31, 0x331b3252, 0x01b36fab,
00339   0x3d5b415b, 0x1a4567e7, 0x3baf6389 };
00340 
00343 /*@observer@*/ /*@unchecked@*/
00344 static uint32 spp_32[] =        /* primes 3 to 739 */
00345 { 0x02c85ff8, 0x70f24be8, 0x0f62b1ba, 0x6c20bd72,
00346   0xb837efdf, 0x121206d8, 0x7db56b7d, 0x69fa4c02,
00347   0x1c107c3c, 0xa206fe8f, 0xa7080ef5, 0x76effc82,
00348   0xf9b10f57, 0x50656b77, 0x94b16afd, 0x70996e91,
00349   0xaef6e0ad, 0x15e91b07, 0x1ac9b24d, 0x98b233ad,
00350   0x86ee0555, 0x18e58e56, 0x638ef18b, 0xac5c74cb,
00351   0x35bbb6e5, 0xdae2783d, 0xd1c0ce7d, 0xec4fc70e,
00352   0x5186d411, 0xdf36368f, 0x061aa360, 0x11f30179 };
00353 
00356 /*@observer@*/ /*@unchecked@*/
00357 static uint32 spp_33[] =        /* primes 3 to 761 */
00358 { 0xd0440ea6, 0x8b382bcb, 0x75b4df8b, 0x6f8aa6cd,
00359   0x494daee4, 0x38b1922e, 0x46cef6ca, 0xdc74a93e,
00360   0xdf45643d, 0x05cc1aa5, 0x556f9c72, 0x0682676d,
00361   0x6668f9c1, 0x89284c78, 0xa770e3a8, 0x423b3833,
00362   0x96c4b063, 0xdb37bced, 0xd891a10f, 0x99328d8a,
00363   0x7c863078, 0xbd323cbc, 0x5ccea379, 0x252d31d3,
00364   0x39d2a084, 0x1717596a, 0x005fbd71, 0xa171925c,
00365   0x902bfb88, 0x6d99e44c, 0xb3a33020, 0xf05cadbe,
00366   0x4a8014ad };
00367 
00370 /*@observer@*/ /*@unchecked@*/
00371 static uint32 spp_34[] =        /* primes 3 to 787 */
00372 { 0x16af5c18, 0xa2bef8ef, 0xf2278332, 0x182d0fbf,
00373   0x0038cc20, 0x5148b83d, 0x06e3d7d9, 0x32828b18,
00374   0xe11e0940, 0x28c7eaed, 0xa3395017, 0xe07d8ae9,
00375   0xb5940604, 0x51d05f93, 0x084cb481, 0x663c94c6,
00376   0xff980dde, 0xccdb42ad, 0x37097f41, 0xa7837fc9,
00377   0x5afe3f18, 0xad76f234, 0x83ae942e, 0x0f0c0bc6,
00378   0xe4001612, 0x3189872b, 0xe58f6dfc, 0x239ca28f,
00379   0xb0cfbf96, 0x4c8f27ce, 0x05d6c77a, 0x01f9d332,
00380   0x36c9d442, 0xad69ed33 };
00381 
00384 /*@observer@*/ /*@unchecked@*/
00385 static uint32 spp_35[] =        /* primes 3 to 811 */
00386 { 0x02c30b50, 0xedc2e94a, 0x3940a943, 0x968984e8,
00387   0x5a132fca, 0x78aedf5b, 0x4e307eec, 0xec19323e,
00388   0x71957e6e, 0xc70aab41, 0x43eb94a6, 0x20e9ca78,
00389   0x25d112d2, 0x055a3562, 0x1629b4b7, 0xb9208518,
00390   0x395b967a, 0xa4b564f8, 0x307459f7, 0x851d00e0,
00391   0x89d845dc, 0xa8e9423d, 0x2f0293bf, 0xdf0a3123,
00392   0xa1719e4c, 0xe4c577b3, 0x485ede33, 0xdd79a1ad,
00393   0xb6f9d10c, 0x8707cd1c, 0x2006396a, 0x192645b9,
00394   0x105ad4a4, 0xbd28a578, 0x5394c375 };
00395 
00398 /*@observer@*/ /*@unchecked@*/
00399 static uint32 spp_36[] =        /* primes 3 to 827 */
00400 { 0x005bfd25, 0x83ab7a44, 0x13d4df0f, 0x537c686c,
00401   0xa8e6b583, 0xe491130e, 0x96dfcc1c, 0x05ba298f,
00402   0x8701314b, 0x45bf6ff4, 0xecf372ff, 0xe78bccdf,
00403   0xfc18365a, 0x6ae5ca41, 0x2794281f, 0xbcc762f1,
00404   0x8ca1eb11, 0xfc8efe0b, 0x6bb5a7a0, 0x9954e758,
00405   0x074256ad, 0x443a8e4b, 0xaa267515, 0x4c43d626,
00406   0x46411944, 0x6e683d08, 0xd4683db5, 0x757d1199,
00407   0x9513a9cb, 0xe3e67e3a, 0xe501c1c5, 0x22aa8ba9,
00408   0xf9557895, 0x89161feb, 0xc69941a1, 0x47aa9685 };
00409 
00412 /*@observer@*/ /*@unchecked@*/
00413 static uint32 spp_37[] =        /* primes 3 to 857 */
00414 { 0x2a89d844, 0x7bf83428, 0x8464b909, 0x31ce3aaa,
00415   0xed0c2683, 0xb26f15e4, 0x32e95677, 0x65036627,
00416   0x80802634, 0x4328b107, 0x89fb23c6, 0x11b484ca,
00417   0xcd937f07, 0x65e0f5df, 0xc8f9a3a2, 0xc7aac35f,
00418   0x3e8a8a35, 0x26515cc0, 0x38c822e0, 0x7a1bd893,
00419   0x852c7ec0, 0xc01d7303, 0x90f69c22, 0xf56ba6cc,
00420   0xd90063cf, 0x72d6ad3d, 0x7a0a7455, 0xef28f5c6,
00421   0x1af3825a, 0x536b8464, 0xe90b2d32, 0x9e831029,
00422   0x638a6241, 0x8946766c, 0x6392ec57, 0x9bd0c31a,
00423   0xb4ce65ab };
00424 
00427 /*@observer@*/ /*@unchecked@*/
00428 static uint32 spp_38[] =        /* primes 3 to 877 */
00429 { 0x06706918, 0xe8355b7f, 0xfd3f024d, 0xa6b012e2,
00430   0xbb7338f3, 0x0d51a968, 0x0f3d9120, 0x35ed70e0,
00431   0x2d38d422, 0xe41812d4, 0xe29d637b, 0x318ce6f4,
00432   0xea117321, 0xce8b712d, 0xcca9345f, 0xd03ccaf5,
00433   0x2e75dafc, 0xda909cd4, 0xb41a9f87, 0x53c8df3d,
00434   0x284198bc, 0xb759d059, 0x94136057, 0x2b7ab25f,
00435   0x396b9fa3, 0x7ae0a200, 0xd998ea09, 0x167edc30,
00436   0xf9d2c45c, 0x7e487029, 0x92750098, 0x3f7fb4e8,
00437   0xe85d8e94, 0x34a37006, 0x8cebc960, 0x60ab2f87,
00438   0x81efeb18, 0x2d0e724b };
00439 
00442 /*@observer@*/ /*@unchecked@*/
00443 static uint32 spp_39[] =        /* primes 3 to 887 */
00444 { 0x0108d441, 0xce330894, 0xff143672, 0x5fee20c5,
00445   0x9b8fb49f, 0xbb29ad13, 0x5f0888b0, 0x59181b63,
00446   0x54380731, 0x8906204b, 0x7e16cc5e, 0x2d8c613b,
00447   0x4414b03a, 0x30587c32, 0xa08bbc57, 0x95f63e1e,
00448   0x6f237e7c, 0xdfc70204, 0xdd20d5d2, 0xd93a0fcb,
00449   0xd54d4e92, 0xd750c3c8, 0x4b276eca, 0x9081b543,
00450   0xa8979c2b, 0xb14e3fa1, 0x7c87d031, 0x300588b2,
00451   0x6b1aa738, 0xbe02e7b4, 0x57a9ed5f, 0x341b72e6,
00452   0x19296afb, 0x2ae2f6b0, 0xf6f00832, 0x9e0d7b8f,
00453   0x61a10c17, 0xa07a962e, 0x5bc81157 };
00454 
00457 /*@observer@*/ /*@unchecked@*/
00458 static uint32 spp_40[] =        /* primes 3 to 929 */
00459 { 0xa9e9591f, 0x7815617e, 0xcabe352f, 0xa13445c4,
00460   0xf8e319ba, 0x63042e1c, 0xb0a017d0, 0xe729a699,
00461   0x5480da4e, 0x5091cab4, 0x12910cf4, 0x7bb0f24e,
00462   0x5e1db412, 0x64b9f96a, 0x2b327e90, 0x1d9d0a39,
00463   0x12659a52, 0xd3792d52, 0x991bfa96, 0x4fe7d212,
00464   0x60374c24, 0xa04de69d, 0xf5d4e46b, 0x249cafc7,
00465   0x347c6181, 0xbd6dc6b8, 0x13a29dc6, 0xd4f785ac,
00466   0x78066355, 0x13530cd5, 0xdb94de48, 0x58c157f0,
00467   0x30b96bfb, 0x6475393b, 0x5f43a549, 0xd95c5619,
00468   0x7e274850, 0xad1a6d18, 0xb5eaa41d, 0xd42fda55 };
00469 
00472 /*@observer@*/ /*@unchecked@*/
00473 static uint32 spp_41[] =        /* primes 3 to 947 */
00474 { 0x2108556d, 0x64bbc9f2, 0xa87149a3, 0x26013838,
00475   0x4d8e761d, 0xab793496, 0x415dad5b, 0xa6682448,
00476   0xe3c8495c, 0xd3f2e881, 0xf3546b54, 0xb8b14068,
00477   0x97668326, 0xe4aa5c56, 0xe8b03fe7, 0x32b53f8b,
00478   0xe55d11c4, 0xfce09e57, 0xee4d8232, 0x1447c16b,
00479   0xe0e1a32d, 0x54972732, 0x5b58b113, 0x136127eb,
00480   0xf48c987d, 0x6532476f, 0x8800deab, 0x4b93a717,
00481   0x6a7cdc07, 0xf51ff3ef, 0x8fdc7d30, 0x289949c2,
00482   0xad7f1d56, 0xe40ca555, 0xa3a33043, 0x74bc64b1,
00483   0x546974cb, 0x927a6b4e, 0x85bf34af, 0x54cd54d6,
00484   0xbbec2afb };
00485 
00488 /*@observer@*/ /*@unchecked@*/
00489 static uint32 spp_42[] =        /* primes 3 to 971 */
00490 { 0x06e1d136, 0xcb78cac5, 0x4da4bfcb, 0x6f2c4a24,
00491   0xfcf3796b, 0x77719c31, 0xd2791586, 0x0001f03e,
00492   0x4347621b, 0xf62577e0, 0x280ebfdb, 0x77b4f1e9,
00493   0x0f954eca, 0xfd198609, 0x68629be9, 0x1424c37a,
00494   0x8f320a34, 0x444953d5, 0x2c278d64, 0x85238798,
00495   0x709d0063, 0xe3fa8623, 0xea24bf2a, 0x2c5278e7,
00496   0x4460d05a, 0x0a708bd9, 0xc019d632, 0xe39e7300,
00497   0x22b9dbb9, 0x13df73cf, 0xb959dffe, 0x348f9623,
00498   0xf697a822, 0xf4a11320, 0xbd044ecc, 0x74878f53,
00499   0x0d57d0f0, 0x76647b0a, 0xb191f543, 0xdc08c392,
00500   0x3167e5ee, 0x56c66847 };
00501 
00504 /*@observer@*/ /*@unchecked@*/
00505 static uint32 spp_43[] =        /* primes 3 to 991 */
00506 { 0x0186695f, 0xa95755fc, 0xe74a9a4e, 0x8fbc30df,
00507   0x119e4901, 0x7edb320f, 0xe8114129, 0xb3bddd0d,
00508   0x2b0cf0f7, 0x2306fb1d, 0x6a5cae26, 0xe4a286ce,
00509   0xe1acd2fb, 0x5e6770b2, 0xc58355ca, 0x1c782114,
00510   0xb05f881d, 0x090a7fcb, 0xe043ebaa, 0x592672ae,
00511   0x9e0335e3, 0xc77acab9, 0xc4aeb4cb, 0xdc1f1341,
00512   0x20257620, 0x7c2ecd85, 0x130f3c11, 0xcad1192b,
00513   0xb43daff3, 0xfd555877, 0xce47d74b, 0x1e878cfd,
00514   0xd7b779a5, 0xca965949, 0xb03075a8, 0x25f009ab,
00515   0x509f0ff9, 0x5202ec37, 0xe9a0f3f4, 0xdc2d184d,
00516   0x10575170, 0xe3e7d4d0, 0xaf86a76f };
00517 
00520 /*@observer@*/ /*@unchecked@*/
00521 static uint32 spp_44[] =        /* primes 3 to 1013 */
00522 { 0x005ca1a9, 0x2edd0e81, 0x9619289e, 0x1ecfe2d7,
00523   0xf3949eaf, 0x363a5fe8, 0xf6fee01c, 0xcd480490,
00524   0x30a1346a, 0xb83c4967, 0x8c7d5882, 0x6caf81ca,
00525   0x1d02473b, 0xea8ad400, 0xd1ce270a, 0x5743c3cd,
00526   0x892c3bd9, 0x3b84525d, 0x8a42071a, 0x508fdb8f,
00527   0x32952aaa, 0x2384cf5d, 0xf23ed81d, 0x10ac0031,
00528   0xd85d0e95, 0xe3c5bb51, 0x71a0e3f1, 0x2b671f8f,
00529   0xb07965cc, 0x353a784b, 0x78f71968, 0x1326c790,
00530   0x6e2b7f7b, 0x0782848e, 0xeb1aea5b, 0xab10b80e,
00531   0x5b7138fc, 0x36f7989c, 0xe85b07c2, 0xd4d59d42,
00532   0x1541c765, 0xf6c2111d, 0xb82eca06, 0xb437f757 };
00533 
00536 /*@observer@*/ /*@unchecked@*/
00537 static uint32 spp_45[] =        /* primes 3 to 1033 */
00538 { 0x5d59c98b, 0x452d0c02, 0x1291e1ef, 0x6ab50494,
00539   0xce984e89, 0xdc563773, 0x96b510a6, 0xeef593cb,
00540   0x73e4eb74, 0x6a1c83ef, 0x9a7bff75, 0x7ee6e25a,
00541   0xe12d86af, 0x743e83ad, 0x0f28e9c6, 0x0aee1694,
00542   0xf5bd9a93, 0xd9e9dc26, 0xd1ed4b29, 0xff2f3094,
00543   0xd431b844, 0xe0cea92f, 0x639ebb6f, 0x7107f740,
00544   0x7c23abc1, 0xcc3789e9, 0x4ddb2532, 0x32ecc6c5,
00545   0x0ecbe5e5, 0x32fd5097, 0x49cc5252, 0x2730c08e,
00546   0x1f7117c2, 0x71c83657, 0x087f4608, 0xe003e4f6,
00547   0x7cb9e029, 0xd33f00ae, 0xd3dad2a0, 0x76735950,
00548   0x7da17074, 0xb23e9701, 0x7e0e9f7e, 0x2ed03221,
00549   0x76712827 };
00550 
00553 /*@observer@*/ /*@unchecked@*/
00554 static uint32 spp_46[] =        /* primes 3 to 1051 */
00555 { 0x18e5b310, 0x229f618d, 0xe0f54782, 0xf57fff33,
00556   0x10546ba8, 0xefc0a69c, 0xac4b573b, 0x749cc43d,
00557   0xd3ba4df6, 0x1fe2800d, 0x733f4eb7, 0x19a6ea7f,
00558   0xa88aebf2, 0xd35b26c8, 0x6e89fe0b, 0x27e198de,
00559   0xe12a14da, 0x03cef215, 0xe6651c60, 0xbe9cf337,
00560   0x3620f4ab, 0xa453eeb9, 0xeb439ba0, 0x79201376,
00561   0x0e3cc7f8, 0x722f09a4, 0x685a5556, 0xb4efd158,
00562   0xb27a6b79, 0xb15f161f, 0xecf3fd80, 0x2767da7a,
00563   0x37ceb764, 0xbebfcc2b, 0x2d833be0, 0x0b21bb68,
00564   0xeab326b9, 0xebb20cc2, 0xd76273ed, 0xefa152ad,
00565   0x531bccbf, 0x17e3c78d, 0x5c43d8f6, 0x866ad640,
00566   0xfdbbba0f, 0xe997b27b };
00567 
00570 /*@observer@*/ /*@unchecked@*/
00571 static uint32 spp_47[] =        /* primes 3 to 1069 */
00572 { 0x06fd3257, 0x047a7639, 0xcb2cfcfb, 0x193180fe,
00573   0x1f21979a, 0x2376042b, 0x6b2809ba, 0x216e6d5b,
00574   0x57fec6ff, 0x96b878bb, 0xe1d4371b, 0x2f53c7e0,
00575   0x036c8309, 0x2f6b0512, 0x7416844f, 0xbdc36a56,
00576   0xa1d7ae59, 0x332552e8, 0xe32f4324, 0xdc90f2d8,
00577   0x546904d8, 0x3b8f0e24, 0x8df97f60, 0x7af99875,
00578   0xae419d8e, 0x2954463b, 0x1f4aef0c, 0x52a102b4,
00579   0xccca2b78, 0x9d2b46c2, 0x0fb3c949, 0x49cbafc5,
00580   0x5ec2b085, 0x03b5beb4, 0x6b6eb1d1, 0xed78e5f2,
00581   0x398baf6c, 0x33ae0815, 0xf0bd3d5b, 0xe1ebbadc,
00582   0x5aa7a694, 0x352122fc, 0xd4c1c770, 0x016d76cb,
00583   0xc050191f, 0x6ce5ab73, 0x6d43113d };
00584 
00587 /*@observer@*/ /*@unchecked@*/
00588 static uint32 spp_48[] =        /* primes 3 to 1093 */
00589 { 0x021bf949, 0x7091b8c3, 0x68cc7c8e, 0x00c1990c,
00590   0x6027481b, 0x79215ac8, 0xa7517749, 0xa2151377,
00591   0x9a993d29, 0x58fcb49a, 0x73680292, 0x68527994,
00592   0xc6cc1928, 0xadd41295, 0x96765f4c, 0xc3141a04,
00593   0x4eb1d615, 0x78881667, 0x57d86187, 0x81813062,
00594   0x03226798, 0x7df0d471, 0x9cd38f1b, 0x7085fca5,
00595   0x334be3a6, 0x003a3ce7, 0xe19aba55, 0x3e80cc5a,
00596   0xe4060eff, 0x6e180666, 0x1da5eeb7, 0xd142d3b2,
00597   0xe40739f1, 0x443dee3a, 0x198637f0, 0x3c062845,
00598   0xeaff3ff2, 0x7ea38d93, 0x44d8a902, 0x22472df0,
00599   0x7dfb5c9c, 0x8ada77cd, 0x0d5b94ef, 0xf021e02e,
00600   0x307d0801, 0x0312d57c, 0xb5d97576, 0x4697842d };
00601 
00604 /*@observer@*/ /*@unchecked@*/
00605 static uint32 spp_49[] =        /* primes 3 to 1109 */
00606 { 0x00a8b455, 0xb6b4a84f, 0x6834364b, 0x936a996f,
00607   0xbceb3f49, 0x88ee2732, 0x24b48131, 0x2357ae12,
00608   0x4d520af5, 0xc87eb399, 0x90944c44, 0xc3a75724,
00609   0x1e3caf22, 0x26585d51, 0x6875521d, 0xb3f466ec,
00610   0xe4117740, 0x5c808598, 0xeded00eb, 0x951faff9,
00611   0xf8d8beee, 0x127c796c, 0x2a358484, 0x8df645d1,
00612   0x31b11876, 0xb04f57d2, 0x4e0c0751, 0x4448e66a,
00613   0x4bd5c496, 0x435274ce, 0x9a059e30, 0xb39a47d0,
00614   0x0c6cbf84, 0x8a46fc8c, 0x4bb19382, 0xe2799723,
00615   0x5fb598f1, 0xdfb21e4a, 0x05b2eeb2, 0xfa25db86,
00616   0x5183ce51, 0xcf330c32, 0xe2749deb, 0x4b7d3fd7,
00617   0x9781307a, 0xc1aee399, 0x0451d911, 0xc9204d5e,
00618   0x80edaf17 };
00619 
00622 /*@observer@*/ /*@unchecked@*/
00623 static uint32 spp_50[] =        /* primes 3 to 1151 */
00624 { 0xfa1bd62b, 0xaae1e767, 0x47535af3, 0x830fc07d,
00625   0xebcf3ef7, 0xe5a8e46b, 0x8937c4af, 0xe02aef0a,
00626   0xce420c7b, 0x2c3f2fac, 0xb9dc94e5, 0x100a7191,
00627   0xb47cf523, 0x520f613b, 0xee8e095a, 0x7b06d781,
00628   0xb6204bde, 0x1648e17f, 0x0f1bd4ab, 0xa00f7e90,
00629   0xd8fc2a05, 0xf5f1e832, 0x6e88a4a6, 0x7e73cae1,
00630   0xc4a93d89, 0xad6b301b, 0x1f185b13, 0x0246ab44,
00631   0x5cadc384, 0x931189b5, 0x566b3ed9, 0xdafba4e6,
00632   0x59f5446e, 0x5a70c8d1, 0x4626b66d, 0x0f1ccfbf,
00633   0xd4238b68, 0x84af7dd3, 0xa91d2063, 0xceb2c2f7,
00634   0xf273b1da, 0x4cb542ea, 0x62c624cf, 0x4fcb0486,
00635   0x138b42a3, 0xc1d9593c, 0xe1254fb3, 0x214d2b08,
00636   0x52532bc5, 0x28bc6467 };
00637 
00640 /*@observer@*/ /*@unchecked@*/
00641 static uint32 spp_51[] =        /* primes 3 to 1171 */
00642 { 0x5b7091ea, 0xdbc63f00, 0x64dd01de, 0x204ee72f,
00643   0xc4644db7, 0x573e04ee, 0x706df728, 0x7a49af78,
00644   0xc5b99680, 0x528566bc, 0x17d57a00, 0x16a5b12e,
00645   0xf30fa9e3, 0xa1d437c8, 0xbf8e3283, 0x3eeb4036,
00646   0xaf3dfa3d, 0xd69f4d6a, 0xae6b7947, 0x18e2e8fa,
00647   0xafccb2a5, 0xf3b3ed57, 0xaac15fb8, 0xd04f7035,
00648   0x0f9edc0e, 0xd868ec8d, 0x430f42ab, 0xad8cf315,
00649   0xee97237c, 0x6df5577e, 0x5a2857d5, 0xc6e41cfc,
00650   0x1557e427, 0xafc62698, 0x9703722f, 0x50f10c60,
00651   0x78579c80, 0x32f8bec2, 0x5bbce21a, 0xa20c3cdb,
00652   0xdbb80d64, 0x31c06f68, 0xa743d08d, 0x220c0f0a,
00653   0x1fbb5766, 0xb6977732, 0x3f869dd0, 0xe286a091,
00654   0x7e3f520e, 0xc3203bce, 0x170ef097 };
00655 
00658 /*@observer@*/ /*@unchecked@*/
00659 static uint32 spp_52[] =        /* primes 3 to 1193 */
00660 { 0x239afcd4, 0x38799705, 0xab8a0cda, 0x4802bc8f,
00661   0xb0e87f44, 0xa568f618, 0x7c604708, 0xdfb79072,
00662   0xe24b49cb, 0x8b2ac531, 0x005cf298, 0x2437b16e,
00663   0x027fa014, 0x14e3dbf5, 0xbf766811, 0x66e276ff,
00664   0xcf676855, 0x0bc1cd9a, 0x1b387eba, 0xaa8550ae,
00665   0xfc10c69c, 0x372a0254, 0xb84666ff, 0x35044b9a,
00666   0xa34fcf7c, 0x817b33f3, 0x7088a289, 0xa17891a7,
00667   0xe66f88e8, 0xec2ba784, 0xb2a09a91, 0x02609726,
00668   0x17a3dbea, 0x8463439d, 0x47972d09, 0xb0e63752,
00669   0xbac58d33, 0x9b402dc1, 0xa0991554, 0x3360cd68,
00670   0x4df24e43, 0x7487571d, 0xfaf68f4f, 0xe0a93546,
00671   0x66aa84bf, 0x84d4448d, 0x21190291, 0x66db27bd,
00672   0x515599cd, 0xcd147810, 0x3acf73e7, 0xfe62aed9 };
00673 
00676 /*@observer@*/ /*@unchecked@*/
00677 static uint32 spp_53[] =        /* primes 3 to 1217 */
00678 { 0x0eb29f45, 0x5fc46bf0, 0xd4857e41, 0xa0059da0,
00679   0xda0b3770, 0xf445bac2, 0x37decad9, 0x954f2a17,
00680   0x849520eb, 0x001349bf, 0xf0264427, 0xb01519ec,
00681   0xf6fdb496, 0x80797a72, 0x17df3f5e, 0x95dea2d3,
00682   0xfded40a1, 0x3bcd8ac6, 0x0af97a12, 0x43383501,
00683   0x915ba38c, 0x90ec4f69, 0x2f931a60, 0x56bf7e42,
00684   0xd2969fab, 0xd442987c, 0x62e0fe9e, 0xaa412cba,
00685   0x8335fe9d, 0x33343d9f, 0x760e9e43, 0xf2b0f8dc,
00686   0xbe1e28ac, 0xa0ce2864, 0x5db05820, 0x71a88a56,
00687   0x4013a0f7, 0xc3d72268, 0x6e2fb29a, 0xc2d23e4e,
00688   0x6ad5ff62, 0x99a85da1, 0x535ff17b, 0x0e26402a,
00689   0xf5669a3d, 0x513660ce, 0x800afdf9, 0xe6ef66e1,
00690   0x9a202974, 0xa1069be2, 0xd54ceff7, 0x8e333c48,
00691   0x4ebbe265 };
00692 
00695 /*@observer@*/ /*@unchecked@*/
00696 static uint32 spp_54[] =        /* primes 3 to 1231 */
00697 { 0x0654f0d4, 0xcdacb307, 0x5419612f, 0xae3cf746,
00698   0xfbab751f, 0xd0887955, 0x28adc68d, 0x26f32877,
00699   0xeb1b772d, 0xb48e49f6, 0xcb445987, 0xc4966560,
00700   0xdff84737, 0x02bb0fd4, 0xf8b68b5c, 0xe2d496a6,
00701   0x0dc7d7e4, 0x3c3cb0bf, 0x72665c6e, 0x4c86a7ce,
00702   0xb78c9da4, 0x0f4d90a8, 0xf5dfe2a4, 0xdc559b8a,
00703   0xba10a63a, 0x0ca25d3a, 0xdec2c419, 0x8b688d80,
00704   0x71c05d3b, 0x694f19de, 0xda32955f, 0x77fbb577,
00705   0x27eb6521, 0x40495e56, 0x2f4a13e8, 0xb648daf2,
00706   0x13d1da75, 0xe3f04bb0, 0x43fedcd2, 0xb2a0cd30,
00707   0xa4339e3a, 0x03b7f3a0, 0xe02a31c2, 0x8394368c,
00708   0x7f73bbf3, 0x2712e69e, 0x7ac58373, 0xe5f7c7e7,
00709   0x55e0d645, 0x628c5475, 0x6217c0bd, 0xf119900b,
00710   0x05ea71dd, 0x714fd2c9 };
00711 
00714 /*@observer@*/ /*@unchecked@*/
00715 static uint32 spp_55[] =        /* primes 3 to 1259 */
00716 { 0x02de1de4, 0xcbca29fc, 0x94a50bb7, 0xae89c417,
00717   0xb8063484, 0x5c71a8c6, 0xa641d997, 0x65355b7e,
00718   0xed63ea84, 0xeaeead3c, 0x2a49b4d2, 0xefdd333e,
00719   0xbc90594b, 0x30eab1fb, 0x519151b2, 0x536ef5a7,
00720   0x40b8e2d9, 0x2c02ffd5, 0x149dc0db, 0xcb0416cf,
00721   0xf8b08c27, 0xcc47095e, 0xbbe5263c, 0x327da58a,
00722   0xcd5825d9, 0x3a0ac60e, 0x7a667d47, 0x084d08aa,
00723   0x5c2449e0, 0x65b7f051, 0xc34d6fb8, 0xac5a5d99,
00724   0xd082950c, 0x11650560, 0x4f2fa1de, 0xf26e51ea,
00725   0xa4ea5ac2, 0x87e2f953, 0xcdfc4d30, 0xf05d6553,
00726   0xa2a28858, 0xea28dc4d, 0x24ae0063, 0xa49c8d44,
00727   0xeedc858f, 0x55e16f54, 0xf9c3f019, 0x6a9c92c9,
00728   0x7b685023, 0x3f0d9c13, 0x7f7c114d, 0xbe550751,
00729   0xbc8560cb, 0x746a4b6c, 0x373cde1f };
00730 
00733 /*@observer@*/ /*@unchecked@*/
00734 static uint32 spp_56[] =        /* primes 3 to 1283 */
00735 { 0x01662c66, 0xdab7a4fa, 0xdba4265a, 0xc2075912,
00736   0x59e9c885, 0xe1330cb6, 0xc91bee92, 0xf1b334ff,
00737   0x384f827c, 0xc8057aa7, 0xc3b65fc6, 0xde53dcac,
00738   0x2db6d790, 0x3febbe07, 0xcc401232, 0x6b128eb7,
00739   0x1afd3136, 0xa9e7f786, 0x14648da1, 0x7b4f50c7,
00740   0xbd4129ca, 0x746dab21, 0x09583797, 0xfc1c2ecd,
00741   0x4c0768a8, 0x1892bd16, 0xdfea8227, 0xbcb2b8bf,
00742   0x168a1452, 0x370b0863, 0xb299d088, 0x8434c213,
00743   0x2383a6c7, 0xb6b4bf20, 0x5addc8da, 0x76d2b172,
00744   0xb416f5b0, 0xb9a38d87, 0x738c1cca, 0x3fe33dd2,
00745   0xf9b7570e, 0x3f663f8b, 0x34169076, 0x51b1dd42,
00746   0x2192331d, 0x9436304a, 0x0303422f, 0x4d420389,
00747   0x4548a055, 0x62ed1c09, 0x1a63309b, 0xf1a9df8b,
00748   0xf0c59af9, 0x12a62c22, 0xe1e1f49b, 0xb0115c17 };
00749 
00752 /*@observer@*/ /*@unchecked@*/
00753 static uint32 spp_57[] =        /* primes 3 to 1297 */
00754 { 0x00b3fde4, 0xe9dbc2a2, 0x1c8f4d4b, 0x53b0ff59,
00755   0x643cf537, 0x88f9d4ba, 0x69472171, 0x6a2f33d5,
00756   0xa93b03b2, 0x59142a0e, 0x117006bc, 0x8b4e1475,
00757   0x1adf80d1, 0x96c20ffd, 0xfa1775f1, 0x83b2df43,
00758   0x1c766011, 0xdefc6c34, 0xc6bfafcd, 0xd51ef8ef,
00759   0x253052b2, 0xc818df16, 0x37372435, 0xe9e55783,
00760   0x6c7d476d, 0x966ec455, 0x1ef8d32f, 0x7d687828,
00761   0xc978db5a, 0xabf1cc69, 0x74e86c65, 0x260bec72,
00762   0x1a609875, 0x6d5942ef, 0x4d4d8b42, 0x6a9cd4fb,
00763   0xe0030023, 0xd9bf209b, 0x4a93c089, 0xc4f634b1,
00764   0xd5463616, 0x33307dbf, 0x127489d6, 0xaa674108,
00765   0xe2c74fd3, 0x63aba6a2, 0x9f2f887d, 0xfc8b13a6,
00766   0xbb230a35, 0x390669ff, 0x22f8243b, 0xbc59cf3d,
00767   0x58bafd1a, 0xc6f2f456, 0xe938c1f8, 0x4051aadc,
00768   0x54d4a035 };
00769 
00772 /*@observer@*/ /*@unchecked@*/
00773 static uint32 spp_58[] =        /* primes 3 to 1307 */
00774 { 0x005cda0c, 0x54b07f4f, 0xff0caca0, 0x7cc89b95,
00775   0x1c021191, 0x164be693, 0x6665357e, 0xbb2f689c,
00776   0x7157ea4f, 0x98037ce1, 0x5aca14ca, 0x3cf1a386,
00777   0xb03e831e, 0xe09a8d5c, 0x48d51f5e, 0x6646ed8a,
00778   0x7ec2b955, 0x216587f0, 0x7f3c42ee, 0x06ae3844,
00779   0x4c776b8c, 0x3ef32747, 0x97cd2ac1, 0xc7cce7ec,
00780   0xe75bb029, 0x0f5b5a0e, 0x2c96c460, 0x0c678a21,
00781   0x0d992d36, 0xd441b1fd, 0x682adf0e, 0xf289947e,
00782   0x6d3de1a2, 0xaf0ca945, 0x859aa1f2, 0xb2bb793d,
00783   0x351dbebf, 0xe05144ee, 0xfe9c752d, 0x75ec602c,
00784   0x0e0344dd, 0xcfcb642b, 0x6cfc8722, 0x19d69873,
00785   0xb8c4ace3, 0xffd460e9, 0x43d903b4, 0x5de9d402,
00786   0x958a41fb, 0x5e008a94, 0xc9361081, 0x4e5e2811,
00787   0xd052c10a, 0xbfc67bf6, 0x915d4435, 0x2688091b,
00788   0x1eb1c711, 0x7c91eae5 };
00789 
00792 /*@observer@*/ /*@unchecked@*/
00793 static uint32 spp_59[] =        /* primes 3 to 1327 */
00794 { 0x0031fc6d, 0x6918c954, 0x9fe61e37, 0xe79cea8a,
00795   0xe12d234b, 0x7642915b, 0x85e4b88b, 0x83eeba5f,
00796   0x429d8086, 0x9a31c342, 0x0020beb9, 0xbc48ece8,
00797   0xcb7bb572, 0xad3a8e34, 0x085a4765, 0x6ba28651,
00798   0xad8a45d5, 0x26ea9c98, 0x90740760, 0xca7bf7e9,
00799   0x9acf6665, 0xc6a9232a, 0x720b8d78, 0x1f51a8b2,
00800   0xdfcbe4ee, 0xa4a48126, 0xad4a6fd8, 0xb5a0c187,
00801   0x12021d6c, 0x3ca2c624, 0xd477495f, 0x11752cc7,
00802   0x77c2b465, 0x8b3cfc3f, 0x2cb0ab3c, 0xc70277e3,
00803   0xd1d97a12, 0xebc6b0db, 0xfe7ad411, 0xdede9e15,
00804   0x905166d9, 0x403ae854, 0x9432b6a4, 0xf45d1540,
00805   0xca51bffd, 0xf107b16c, 0x08deae8e, 0x49bc15e8,
00806   0xd1d3ac9c, 0x2a76465a, 0xe778cc84, 0x810878db,
00807   0xfad8b7e5, 0xd5151c83, 0x9045920b, 0xfa0cecd0,
00808   0x43e94546, 0xee4f4361, 0x84901bb5 };
00809 
00812 /*@observer@*/ /*@unchecked@*/
00813 static uint32 spp_60[] =        /* primes 3 to 1381 */
00814 { 0xa0604bc5, 0x4c251ade, 0xcf22bf07, 0x5a150bb1,
00815   0x2a67d65a, 0x5045c183, 0x17246627, 0x0d72a8c6,
00816   0x3e2dd1c4, 0x6694a251, 0xf55bca5e, 0x7d834c87,
00817   0x2a8d10e5, 0xea91ba4d, 0xcce166f1, 0x6b1be0ef,
00818   0xba025bf3, 0x62f29284, 0xa36db516, 0x75c7d25e,
00819   0xac751992, 0x5560c7a1, 0xc7047093, 0x8bdf2818,
00820   0xed42d042, 0x53130bef, 0x0d92e596, 0x844e073b,
00821   0xdd40bd15, 0x6f433f09, 0xbdfd3e38, 0x769a485c,
00822   0xf29380b7, 0x9c18989c, 0xed0e6ec4, 0x3bcc7b73,
00823   0x087e1fb9, 0x4e8cf2d3, 0x475c7760, 0x5c707f6b,
00824   0x31f7217c, 0x4c628da2, 0xe3263e30, 0xa83c1066,
00825   0x1378f415, 0x33ca7d71, 0x5d4e2b87, 0xc0e142ba,
00826   0x462e6ffb, 0x506e09f9, 0x7850c73e, 0x4b3f7a24,
00827   0xca98bda0, 0x5c0c6ac6, 0x666daad0, 0x14d2ff3f,
00828   0x7138fa68, 0xddd5e9f0, 0xe92edcaa, 0x62b56483 };
00829 
00832 /*@observer@*/ /*@unchecked@*/
00833 static uint32 spp_61[] =        /* primes 3 to 1423 */
00834 { 0x68bd8015, 0x91071573, 0x8a205b51, 0xe1be9357,
00835   0xdab961de, 0x59c9e43c, 0xb9becf7a, 0x8adba9a9,
00836   0x926a87bb, 0x7f574190, 0x3ee07b97, 0x83b5ed87,
00837   0x503ee854, 0xbfc61ca4, 0x9531565e, 0x4e8136f5,
00838   0xdb315f85, 0x3ae9f609, 0x2deebbac, 0x45e36b1b,
00839   0x1f3a6d76, 0xe4e758c0, 0x2477bd33, 0x40b9cf8e,
00840   0xe1815167, 0x132e13ab, 0x82cf7f08, 0x51b86b6f,
00841   0xfd7cfaea, 0x9b7b7dcc, 0xcd7c9d57, 0x9ccb5269,
00842   0xa01e7ef9, 0x52ec1995, 0xbc6df02c, 0x649435e7,
00843   0x3e12d47d, 0xc484c579, 0xda72631f, 0x976b8eda,
00844   0x270cc80b, 0x56141511, 0xf857bc1c, 0x898e8aeb,
00845   0xb836ca21, 0x2ed0d5cb, 0xcd16c412, 0x81a67e69,
00846   0xbbb68933, 0x5ead39cf, 0xdefe9acb, 0x9721e75c,
00847   0xd59b372e, 0xc91ec67d, 0x0df39398, 0x106914b7,
00848   0xba405fde, 0xe85bb37c, 0xdae528dd, 0xe98d3250,
00849   0xbec22e6b };
00850 
00853 /*@observer@*/ /*@unchecked@*/
00854 static uint32 spp_62[] =        /* primes 3 to 1433 */
00855 { 0x4742fdaf, 0xf7e8231a, 0xded68277, 0x58493423,
00856   0x12b13d2f, 0x5925c539, 0x82d876ef, 0x7ff69e7f,
00857   0x5b4ff04e, 0x8454faea, 0x620dc960, 0x0c65fd57,
00858   0x2aecce4c, 0x9656588f, 0x79dfb5df, 0xd7f99148,
00859   0x196c24df, 0x6d8c704b, 0xd6ffb8d9, 0xcedb8ee8,
00860   0x448d4352, 0xd834cef7, 0xfce9b929, 0x07eeca6a,
00861   0xcc107008, 0xfa118ff7, 0xedcc0b84, 0x207c3eef,
00862   0xdb5ea3ef, 0x89c684d8, 0x89c4187a, 0x10775358,
00863   0xc429d4d2, 0xa76bb2c3, 0x9f406fdc, 0x49dcf4b6,
00864   0xed773586, 0x770e4651, 0xcb63c783, 0x54d2a578,
00865   0x5f52816b, 0x14d29d62, 0x06d952ca, 0x4428030e,
00866   0x2e793590, 0xf75f1d07, 0x79363fa6, 0x047f0c64,
00867   0xf3ed6a91, 0x2dbc4437, 0x673d4184, 0x00d005ca,
00868   0x9ca42ff6, 0x841c84dd, 0xaaff5fb0, 0x87f85954,
00869   0x177c5dc0, 0xfbfbb491, 0xa1e5e03e, 0x5715875c,
00870   0xa02a0fa4, 0x1fde7abd };
00871 
00874 /*@observer@*/ /*@unchecked@*/
00875 static uint32 spp_63[] =        /* primes 3 to 1451 */
00876 { 0x322123be, 0x40a1853c, 0xd02ea217, 0x363a368b,
00877   0xacb2117a, 0x342a5ee6, 0xa03a7fda, 0x4338eaac,
00878   0x9d9cc512, 0xffa944f1, 0x767e0a56, 0xc82c051f,
00879   0xe91415e0, 0x4cfddc19, 0x7f9539ee, 0x3801a5cc,
00880   0x3b68d593, 0xa5a8a3a9, 0x71ccc478, 0x938461f7,
00881   0xe804c928, 0xb3f42839, 0x97fa73a7, 0x09b9ebe5,
00882   0x7cbb88f1, 0xea9754c4, 0xbc0a20c1, 0xe0b7f585,
00883   0x6649a4b8, 0x88eec46b, 0xf86f7ccf, 0xfdecbfbd,
00884   0x46b40b23, 0xcf80aaef, 0xf810bf21, 0x8f793d2d,
00885   0x2722ddc8, 0xc8c87536, 0x66fc2278, 0xb5186905,
00886   0xe9f8220c, 0x0b454fa8, 0xc461c002, 0x80e6882a,
00887   0xb5e77c84, 0xde0b068e, 0xb34cdd5a, 0xa370bc8a,
00888   0x6e38121f, 0x2f3e9009, 0x82df957a, 0x585c307d,
00889   0x9b2b1f9d, 0x732df2a0, 0x1d9e6968, 0xbc23657f,
00890   0x4d152676, 0xe28268ad, 0xf7c026d3, 0x55a2a944,
00891   0xf41bc21f, 0x67b73894, 0x5828ad87 };
00892 
00895 /*@observer@*/ /*@unchecked@*/
00896 static uint32 spp_64[] =        /* primes 3 to 1471 */
00897 { 0x2465a7bd, 0x85011e1c, 0x9e052792, 0x9fff268c,
00898   0x82ef7efa, 0x416863ba, 0xa5acdb09, 0x71dba0cc,
00899   0xac3ee499, 0x9345029f, 0x2cf810b9, 0x9e406aac,
00900   0x5fce5dd6, 0x9d1c717d, 0xaea5d18a, 0xb913f456,
00901   0x505679bc, 0x91c57d46, 0xd9888857, 0x862b36e2,
00902   0xede2e473, 0xc1f0ab35, 0x9da25271, 0xaffe15ff,
00903   0x240e299d, 0x0b04f4cd, 0x0e4d7c0e, 0x47b1a7ba,
00904   0x007de89a, 0xae848fd5, 0xbdcd7f98, 0x15564eb0,
00905   0x60ae14f1, 0x9cb50c29, 0x1f0bbd8e, 0xd1c4c7f8,
00906   0xfc5fba51, 0x66200193, 0x9b532d92, 0xdac844a8,
00907   0x431d400c, 0x832d039f, 0x5f900b27, 0x8a75219c,
00908   0x2986140c, 0x79045d77, 0x59540854, 0xc31504dc,
00909   0x56f1df5e, 0xebe7bee4, 0x47658b91, 0x7bf696d6,
00910   0x927f2e24, 0x28fbeb34, 0x0e515cb9, 0x835d6387,
00911   0x1be8bbe0, 0x9cf13445, 0x799f2e67, 0x78815157,
00912   0x1a93b4c1, 0xeee55d1b, 0x9072e0b2, 0xf5c4607f };
00913 
00914 uint32* mp32spprod[SMALL_PRIMES_PRODUCT_MAX] =
00915 {
00916         spp_01,
00917         spp_02,
00918         spp_03,
00919         spp_04,
00920         spp_05,
00921         spp_06,
00922         spp_07,
00923         spp_08,
00924         spp_09,
00925         spp_10,
00926         spp_11,
00927         spp_12,
00928         spp_13,
00929         spp_14,
00930         spp_15,
00931         spp_16,
00932         spp_17,
00933         spp_18,
00934         spp_19,
00935         spp_20,
00936         spp_21,
00937         spp_22,
00938         spp_23,
00939         spp_24,
00940         spp_25,
00941         spp_26,
00942         spp_27,
00943         spp_28,
00944         spp_29,
00945         spp_30,
00946         spp_31,
00947         spp_32,
00948         spp_33,
00949         spp_34,
00950         spp_35,
00951         spp_36,
00952         spp_37,
00953         spp_38,
00954         spp_39,
00955         spp_40,
00956         spp_41,
00957         spp_42,
00958         spp_43,
00959         spp_44,
00960         spp_45,
00961         spp_46,
00962         spp_47,
00963         spp_48,
00964         spp_49,
00965         spp_50,
00966         spp_51,
00967         spp_52,
00968         spp_53,
00969         spp_54,
00970         spp_55,
00971         spp_56,
00972         spp_57,
00973         spp_58,
00974         spp_59,
00975         spp_60,
00976         spp_61,
00977         spp_62,
00978         spp_63,
00979         spp_64,
00980 };
00981 
00982 int mp32ptrials(uint32 bits)
00983 {
00984         if (bits >= 1854)
00985                 return 2;
00986         if (bits >= 1223)
00987                 return 3;
00988         if (bits >= 927)
00989                 return 4;
00990         if (bits >= 747)
00991                 return 5;
00992         if (bits >= 627)
00993                 return 6;
00994         if (bits >= 543)
00995                 return 7;
00996         if (bits >= 480)
00997                 return 8;
00998         if (bits >= 431)
00999                 return 9;
01000         if (bits >= 393)
01001                 return 10;
01002         if (bits >= 361)
01003                 return 11;
01004         if (bits >= 335)
01005                 return 12;
01006         if (bits >= 314)
01007                 return 13;
01008         if (bits >= 295)
01009                 return 14;
01010         if (bits >= 279)
01011                 return 15;
01012         if (bits >= 265)
01013                 return 16;
01014         if (bits >= 253)
01015                 return 17;
01016         if (bits >= 242)
01017                 return 18;
01018         if (bits >= 232)
01019                 return 19;
01020         if (bits >= 223)
01021                 return 20;
01022         if (bits >= 216)
01023                 return 21;
01024         if (bits >= 209)
01025                 return 22;
01026         if (bits >= 202)
01027                 return 23;
01028         if (bits >= 196)
01029                 return 24;
01030         if (bits >= 191)
01031                 return 25;
01032         if (bits >= 186)
01033                 return 26;
01034         if (bits >= 182)
01035                 return 27;
01036         if (bits >= 178)
01037                 return 28;
01038         if (bits >= 174)
01039                 return 29;
01040         if (bits >= 170)
01041                 return 30;
01042         if (bits >= 167)
01043                 return 31;
01044         if (bits >= 164)
01045                 return 32;
01046         if (bits >= 161)
01047                 return 33;
01048         if (bits >= 160)
01049                 return 34;
01050         return 35;
01051 }
01052 
01055 /*@-boundsread@*/
01056 static void mp32prndbits(mp32barrett* p, uint8 msbclr, uint8 lsbset, randomGeneratorContext* rc)
01057         /*@modifies p @*/
01058 {
01059         register uint32 size;
01060 
01061         if (p == (mp32barrett*) 0 || p->modl == (uint32*) 0)
01062                 return;
01063 
01064         size = p->size;
01065         /*@-noeffectuncon@*/ /* LCL: ??? */
01066         (void) rc->rng->next(rc->param, p->modl, size);
01067         /*@=noeffectuncon@*/
01068 
01069         if (msbclr != 0)
01070                 p->modl[0] &= (((uint32)0xffffffff) >> msbclr);
01071 
01072         p->modl[0] |= (((uint32)0x80000000) >> msbclr);
01073 
01074         /*@-shiftnegative@*/
01075         if (lsbset != 0)
01076                 p->modl[size] |= (((uint32)0xffffffff) >> (32 - lsbset));
01077         /*@=shiftnegative@*/
01078 }
01079 /*@=boundsread@*/
01080 
01085 /*@-boundsread@*/
01086 static int mp32psppdiv_w(const mp32barrett* p, /*@out@*/ uint32* wksp)
01087         /*@globals mp32spprod @*/
01088         /*@modifies wksp @*/
01089 {
01090         /* small prime product trial division test */
01091         register uint32 size = p->size;
01092 
01093         if (size > SMALL_PRIMES_PRODUCT_MAX)
01094         {
01095                 mp32setx(size, wksp+size, SMALL_PRIMES_PRODUCT_MAX, mp32spprod[SMALL_PRIMES_PRODUCT_MAX-1]);
01096                 /*@-compdef@*/ /* LCL: wksp+size undef */
01097                 mp32gcd_w(size, p->modl, wksp+size, wksp, wksp+2*size);
01098                 /*@=compdef@*/
01099         }
01100         else
01101         {
01102                 mp32gcd_w(size, p->modl, mp32spprod[size-1], wksp, wksp+2*size);
01103         }
01104 
01105         return mp32isone(size, wksp);
01106 }
01107 /*@=boundsread@*/
01108 
01113 static int mp32pmilrabtwo_w(const mp32barrett* p, uint32 s, const uint32* rdata, const uint32* ndata, /*@out@*/ uint32* wksp)
01114         /*@modifies wksp @*/
01115 {
01116         register uint32 size = p->size;
01117         register uint32 j = 0;
01118 
01119         mp32btwopowmod_w(p, size, rdata, wksp, wksp+size);
01120 
01121         while (1)
01122         {
01123                 if (mp32isone(size, wksp))
01124                         return (j == 0);
01125 
01126                 if (mp32eq(size, wksp, ndata))
01127                         return 1;
01128 
01129                 if (++j < s)
01130                         mp32bsqrmod_w(p, size, wksp, wksp, wksp+size);
01131                 else
01132                         return 0;
01133         }
01134 }
01135 
01140 static int mp32pmilraba_w(const mp32barrett* p, const uint32* adata, uint32 s, const uint32* rdata, const uint32* ndata, /*@out@*/ uint32* wksp)
01141         /*@modifies wksp @*/
01142 {
01143         register uint32 size = p->size;
01144         register uint32 j = 0;
01145 
01146         mp32bpowmod_w(p, size, adata, size, rdata, wksp, wksp+size);
01147 
01148         while (1)
01149         {
01150                 if (mp32isone(size, wksp))
01151                         return (j == 0);
01152 
01153                 if (mp32eq(size, wksp, ndata))
01154                         return 1;
01155 
01156                 if (++j < s)
01157                         mp32bsqrmod_w(p, size, wksp, wksp, wksp+size);
01158                 else
01159                         return 0;
01160         }
01161 }
01162 
01166 /*@-boundswrite@*/
01167 int mp32pmilrab_w(const mp32barrett* p, randomGeneratorContext* rc, int t, uint32* wksp)
01168 {
01169         /*
01170          * Miller-Rabin probabilistic primality test, with modification
01171          *
01172          * For more information, see:
01173          * "Handbook of Applied Cryptography"
01174          *  Chapter 4.24
01175          *
01176          * Modification to the standard algorithm:
01177          *  The first value of a is not obtained randomly, but set to two
01178          */
01179 
01180         /* this routine uses (size*3) storage, and calls mp32bpowmod, which needs (size*4+2) */
01181         /* (size) for a, (size) for r, (size) for n-1 */
01182 
01183         register uint32  size  = p->size;
01184         register uint32* ndata = wksp;
01185         register uint32* rdata = ndata+size;
01186         register uint32* adata = rdata+size;
01187 
01188         uint32 s;
01189 
01190         mp32copy(size, ndata, p->modl);
01191         (void) mp32subw(size, ndata, 1);
01192         mp32copy(size, rdata, ndata);
01193 
01194         s = mp32rshiftlsz(size, rdata); /* we've split p-1 into (2^s)*r */
01195 
01196         /* should do an assert that s != 0 */
01197 
01198         /* do at least one test, with a = 2 */
01199         if (t == 0)
01200                 t++;
01201 
01202         if (!mp32pmilrabtwo_w(p, s, rdata, ndata, wksp+3*size))
01203                 return 0;
01204 
01205         while (t-- > 0)
01206         {
01207                 /* generate a random 'a' into b->data */
01208                 mp32brnd_w(p, rc, adata, wksp);
01209 
01210                 if (!mp32pmilraba_w(p, adata, s, rdata, ndata, wksp+3*size))
01211                         return 0;
01212         }
01213 
01214     return 1;
01215 }
01216 /*@=boundswrite@*/
01217 
01221 /*@-boundswrite@*/
01222 void mp32prnd_w(mp32barrett* p, randomGeneratorContext* rc, uint32 size, int t, const mp32number* f, uint32* wksp)
01223 {
01224         /*
01225          * Generate a prime into p with (size*32) bits
01226          *
01227          * Conditions: size(f) <= size(p)
01228          *
01229          * Optional input f: if f is not null, then search p so that GCD(p-1,f) = 1
01230          */
01231 
01232         mp32binit(p, size);
01233 
01234         if (p->modl != (uint32*) 0)
01235         {
01236                 while (1)
01237                 {
01238                         /*
01239                          * Generate a random appropriate candidate prime, and test
01240                          * it with small prime divisor test BEFORE computing mu
01241                          */
01242 
01243                         mp32prndbits(p, 0, 1, rc);
01244 
01245                         /* do a small prime product trial division test on p */
01246                         if (!mp32psppdiv_w(p, wksp))
01247                                 continue;
01248 
01249                         /* if we have an f, do the congruence test */
01250                         if (f != (mp32number*) 0)
01251                         {
01252                                 mp32copy(size, wksp, p->modl);
01253                                 (void) mp32subw(size, wksp, 1);
01254                                 mp32setx(size, wksp+size, f->size, f->data);
01255                                 mp32gcd_w(size, wksp, wksp+size, wksp+2*size, wksp+3*size);
01256 
01257                                 if (!mp32isone(size, wksp+2*size))
01258                                         continue;
01259                         }
01260 
01261                         /* candidate has passed so far, now we do the probabilistic test */
01262                         mp32bmu_w(p, wksp);
01263 
01264                         if (mp32pmilrab_w(p, rc, t, wksp))
01265                                 return;
01266                 }
01267         }
01268 }
01269 /*@=boundswrite@*/
01270 
01274 /*@-boundswrite@*/
01275 void mp32prndconone_w(mp32barrett* p, randomGeneratorContext* rc, uint32 size, int t, const mp32barrett* q, const mp32number* f, mp32number* r, int cofactor, uint32* wksp)
01276 {
01277         /*
01278          * Generate a prime p with n bits such that p mod q = 1, and p = qr+1; r = 2s
01279          *
01280          * Conditions: q > 2 and size(q) < size(p) and size(f) <= size(p)
01281          *
01282          * Conditions: r must be chosen so that r is even, otherwise p will be even!
01283          *
01284          * if cofactor == 0, then s will be chosen randomly
01285          * if cofactor == 1, then make sure that q does not divide r, i.e.:
01286          *    q cannot be equal to r, since r is even, and q > 2; hence if q <= r make sure that GCD(q,r) == 1
01287          * if cofactor == 2, then make sure that s is prime
01288          * 
01289          * Optional input f: if f is not null, then search p so that GCD(p-1,f) = 1
01290          */
01291 
01292         mp32binit(p, size);
01293 
01294         if (p->modl != (uint32*) 0)
01295         {
01296                 mp32barrett s;
01297 
01298                 mp32bzero(&s);
01299                 mp32binit(&s, p->size - q->size);
01300 
01301                 while (1)
01302                 {
01303                         mp32prndbits(&s, 1, 0, rc);
01304 
01305                         /*@-usedef@*/ /* s is set */
01306                         if (cofactor == 1)
01307                         {
01308                                 mp32setlsb(s.size, s.modl);
01309 
01310                                 /* if (q <= s) check if GCD(q,s) != 1 */
01311                                 if (mp32lex(q->size, q->modl, s.size, s.modl))
01312                                 {
01313                                         /* we can find adequate storage for computing the gcd in s->wksp */
01314                                         mp32setx(s.size, wksp, q->size, q->modl);
01315                                         mp32gcd_w(s.size, s.modl, wksp, wksp+s.size, wksp+2*s.size);
01316 
01317                                         if (!mp32isone(s.size, wksp+s.size))
01318                                                 continue;
01319                                 }
01320                         }
01321                         else if (cofactor == 2)
01322                         {
01323                                 mp32setlsb(s.size, s.modl);
01324                         }
01325                         else
01326                                 {};
01327 
01328                         if (cofactor == 2)
01329                         {
01330                                 /* do a small prime product trial division test on r */
01331                                 if (!mp32psppdiv_w(&s, wksp))
01332                                         continue;
01333                         }
01334 
01335                         /* multiply q*s into p, multiply by two, then add 1 */
01336                         mp32mul(p->modl, s.size, s.modl, q->size, q->modl);
01337                         (void) mp32multwo(p->size, p->modl);
01338                         (void) mp32addw(p->size, p->modl, 1);
01339 
01340                         /* do a small prime product trial division test on p */
01341                         if (!mp32psppdiv_w(p, wksp))
01342                                 continue;
01343 
01344                         /* if we have an f, do the congruence test */
01345                         if (f != (mp32number*) 0)
01346                         {
01347                                 mp32copy(size, wksp, p->modl);
01348                                 (void) mp32subw(size, wksp, 1);
01349                                 mp32setx(size, wksp, f->size, f->data);
01350                                 mp32gcd_w(size, wksp, wksp+size, wksp+2*size, wksp+3*size);
01351                                 if (!mp32isone(size, wksp+2*size))
01352                                         continue;
01353                         }
01354 
01355                         /* if cofactor is two, test if s is prime */
01356                         if (cofactor == 2)
01357                         {
01358                                 mp32bmu_w(&s, wksp);
01359 
01360                                 if (!mp32pmilrab_w(&s, rc, mp32ptrials(s.size << 5), wksp))
01361                                         continue;
01362                         }
01363 
01364                         /* candidate has passed so far, now we do the probabilistic test on p */
01365                         mp32bmu_w(p, wksp);
01366 
01367                         if (!mp32pmilrab_w(p, rc, t, wksp))
01368                                 continue;
01369 
01370                         mp32nset(r, s.size, s.modl);
01371                         (void) mp32multwo(r->size, r->data);
01372                         mp32bfree(&s);
01373 
01374                         return;
01375                         /*@=usedef@*/
01376                 }
01377         }
01378 }
01379 /*@=boundswrite@*/
01380 
01381 /*@-boundswrite@*/
01382 void mp32prndsafe_w(mp32barrett* p, randomGeneratorContext* rc, uint32 size, int t, uint32* wksp)
01383 {
01384         /*
01385          * Initialize with a probable safe prime of 'size' words, with probability factor t
01386          *
01387          * A safe prime p has the property that p = 2q+1, where q is also prime
01388          * Use for ElGamal type schemes, where a generator of order (p-1) is required
01389          */
01390 
01391         mp32binit(p, size);
01392 
01393         if (p->modl != (uint32*) 0)
01394         {
01395                 mp32barrett q;
01396 
01397                 mp32bzero(&q);
01398                 mp32binit(&q, size);
01399 
01400                 /*@-usedef@*/   /* q is set */
01401                 while (1)
01402                 {
01403                         /*
01404                          * Generate a random appropriate candidate prime, and test
01405                          * it with small prime divisor test BEFORE computing mu
01406                          */
01407 
01408                         mp32prndbits(p, 0, 2, rc);
01409 
01410                         mp32copy(size, q.modl, p->modl);
01411                         mp32divtwo(size, q.modl);
01412 
01413                         /* do a small prime product trial division on q */
01414                         if (!mp32psppdiv_w(&q, wksp))
01415                                 continue;
01416 
01417                         /* do a small prime product trial division on p */
01418                         if (!mp32psppdiv_w(p, wksp))
01419                                 continue;
01420 
01421                         /* candidate prime has passed small prime division test for p and q */
01422                         mp32bmu_w(&q, wksp);
01423 
01424                         if (!mp32pmilrab_w(&q, rc, t, wksp))
01425                                 continue;
01426 
01427                         mp32bmu_w(p, wksp);
01428 
01429                         if (!mp32pmilrab_w(p, rc, t, wksp))
01430                                 continue;
01431 
01432                         mp32bfree(&q);
01433 
01434                         return;
01435                 }
01436                 /*@=usedef@*/
01437         }
01438 }
01439 /*@=boundswrite@*/

Generated on Tue Sep 17 15:59:46 2002 for rpm by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002