randompp.cpp

flint库 RSA算法

  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 odd

LINT 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 p

LINT 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 odd

LINT 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 odd

LINT 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 odd

LINT 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 odd

LINT 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);
}