?? randompp.cpp
字號:
if (p.iseven ()) { p += q; } while (p > pmax) { p = pmin + p % (t + 1); w = p % twotimesq; p += (twotimesq - w) + a; if (p.iseven ()) { p += q; } } while (1 != gcd (p - 1, f) || !p.isprime ()) { Assert (twotimesq < pmax); p += twotimesq; while (p > pmax) { p += sRand_l (&xrstate); p = pmin + p % (t + 1); Assert (p < pmax); w = p % twotimesq; p += (twotimesq - w) + a; Assert (p < pmax); if (p.iseven ()) { p += q; } Assert (p < pmax); } } Assert ((p - a) % q == 0); return p; // p is prime with p = a mod q, ggT (p - 1, f) = 1}// Find random prime number p of length pmin <= p <= pmax// with p = a mod q and gcd (p - 1, f) = 1.// Input parameter: 2 < q prime, a mod q != 0, 0 < f oddLINT ExtendPrime (USHORT l, const LINT& a, const LINT& q, const LINT& f, STATEPRNG& xrstate){ if (l > CLINTMAXBIT) LINT::panic (E_LINT_INV, "ExtendPrime", 1, __LINE__, __FILE__); LINT pmin = LINT(0).setbit (l - 1); LINT pmax = LINT(0).setbit (l); --pmax; return (ExtendPrime (pmin, pmax, a, q, f, xrstate));}// Find strong prime p of length 2^(l-1) <= p <= 2^l - 1// with primes r, s, t, such that// r divides p - 1// t divides r - 1// s divides p + 1//// Input parameter: Binary length l of pLINT StrongPrime (USHORT l, STATEPRNG& xrstate){ if (l >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 1, __LINE__, __FILE__); LINT pmin = LINT(0).setbit (l - 1); LINT pmax = LINT(0).setbit (l); --pmax; return (StrongPrime (pmin, pmax, (l>>2)-8, (l>>1)-8, (l>>1)-8, 1, xrstate));}// Find strong prime p of length 2^(l-1) <= p <= 2^l - 1// with gcd (p - 1, f) = 1 and primes r, s, t such that// r divides p - 1// t divides r - 1// s divides p + 1//// Input parameter: Binary length l of p,// 0 < f oddLINT StrongPrime (USHORT l, const LINT& f, STATEPRNG& xrstate){ if (l >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 1, __LINE__, __FILE__); LINT pmin = LINT(0).setbit (l - 1); LINT pmax = LINT(0).setbit (l); --pmax; return (StrongPrime (pmin, pmax, (l>>2)-8, (l>>1)-8, (l>>1)-8, f, xrstate));}// Find strong prime p of length 2^(l-1) <= p <= 2^l - 1// with gcd (p - 1, f) = 1 and primes r, s, t such that// r divides p - 1// t divides r - 1// s divides p + 1//// Input parameter: Binary length l of p,// Lengths lt, lr and ls of primes t, r and s resp.// lt <~ l/4, lr ~ ls <~ l/2 of l// <~ means: smaller than, close to// 0 < f oddLINT StrongPrime (USHORT l, USHORT lt, USHORT lr, USHORT ls, const LINT& f, STATEPRNG& xrstate){ if (l >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 1, __LINE__, __FILE__); if (lt >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 2, __LINE__, __FILE__); if (lr >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 3, __LINE__, __FILE__); if (ls >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 4, __LINE__, __FILE__); LINT pmin = LINT(0).setbit (l - 1); LINT pmax = LINT(0).setbit (l); --pmax; return (StrongPrime (pmin, pmax, lt, ls, lr, f, xrstate));}// Find strong prime p with pmin <= p <= pmax// with gcd (p - 1, f) = 1 and primes r, s, t such that// r divides p - 1// t divides r - 1// s divides p + 1//// Input parameter: pmin, pmax// 0 < f oddLINT StrongPrime (const LINT& pmin, const LINT& pmax, const LINT& f, STATEPRNG& xrstate){ if (pmin.status == E_LINT_INV) LINT::panic (E_LINT_INV, "StrongPrime", 1, __LINE__, __FILE__); if (pmax.status == E_LINT_INV) LINT::panic (E_LINT_INV, "StrongPrime", 2, __LINE__, __FILE__); if (f.status == E_LINT_INV) LINT::panic (E_LINT_INV, "StrongPrime", 6, __LINE__, __FILE__); // 0 < f muss ungerade sein if (f.iseven ()) LINT::panic (E_LINT_INV, "StrongPrime", 5, __LINE__, __FILE__); int lt = (ld (pmin) >> 2) - 8; int lr = (ld (pmin) >> 1) - 8; int ls = lr; return StrongPrime (pmin, pmax, lt, ls, lr, f, xrstate);}// Find strong prime p with pmin <= p <= pmax// with gcd (p - 1, f) = 1 and primes r, s, t such that// r divides p - 1// t divides r - 1// s divides p + 1//// Input parameters: pmin, pmax,// Lengths lt, lr and ls of primes t, r and s resp.// lt <~ l/4, lr ~ ls <~ l/2 of l// <~ means: smaller than, close to// 0 < f oddLINT StrongPrime (const LINT& pmin, const LINT& pmax, USHORT lt, USHORT lr, USHORT ls, const LINT& f, STATEPRNG& xrstate){ if (pmin.status == E_LINT_INV) LINT::panic (E_LINT_INV, "StrongPrime", 1, __LINE__, __FILE__); if (pmax.status == E_LINT_INV) LINT::panic (E_LINT_INV, "StrongPrime", 2, __LINE__, __FILE__); if (lt >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 3, __LINE__, __FILE__); if (lr >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 4, __LINE__, __FILE__); if (ls >= CLINTMAXBIT) LINT::panic (E_LINT_OFL, "StrongPrime", 5, __LINE__, __FILE__); if (f.status == E_LINT_INV) LINT::panic (E_LINT_INV, "StrongPrime", 6, __LINE__, __FILE__); // 0 < f muss ungerade sein if (f.iseven ()) LINT::panic (E_LINT_INV, "StrongPrime", 5, __LINE__, __FILE__); LINT t = FindPrime (lt, 1, xrstate); LINT r = ExtendPrime (lr, 1, t, 1, xrstate); LINT s = FindPrime (ls, 1, xrstate); LINT p = inv (r,s); // p := r^(-1) mod s p *= r; // p := r^(-1) * r p <<= 1; // p := 2*r^(-1) * r LINT rs = r*s; p = msub (1,p,rs); // p := 1 - 2*r^(-1) * r mod r*s = s*u - r*v mod r*s // mit u := s^(-1) mod r und v := r^(-1) mod s Assert ((p - 1) % r == 0); Assert ((p + 1) % s == 0); p = ExtendPrime (pmin, pmax, p, rs, f, xrstate); Assert ((p - 1) % r == 0); Assert ((p + 1) % s == 0); return p;}// Compatibility functions for prior versions of Blum-Blum-Shub-Generator// not thread-safe!static STATEPRNG xrstate_loc;int seedBBS (const LINT& seed){ if (seed.status == E_LINT_INV) LINT::panic (E_LINT_INV, "seedBBS", 0, __LINE__); xrstate_loc.Generator = FLINT_RNDBBS; return (seedBBS_l (&xrstate_loc.StateBBS, seed.n_l));}LINT randBBS (int l){ return RandLINT (l, xrstate_loc);}LINT randBBS (const LINT& rmin, const LINT& rmax){ return RandLINT (rmin, rmax, xrstate_loc);}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -