Cryptography Reference
In-Depth Information
generation of a prime number
p
within an interval
[
p
min
,p
max
]
satisfying the additional condition
gcd(
p
Function:
−
1
,f
)=1
,
f
an odd positive integer
LINT
findprime(const LINT& pmin,
const LINT& pmax, const LINT& f);
Syntax:
Input:
pmin
: smallest permissible value
pmax
: largest permissible value
f
: odd positive integer, which should be relatively
prime to
p −
1
LINT
prime
p
determined by a probabilistic test
(cf. Section 10.5) with
gcd(
p
Return:
−
1
,f
)
LINT findprime (const LINT& pmin, const LINT& pmax, const LINT& f)
{
if (pmin.status == E_LINT_INV) LINT::panic (E_LINT_VAL, "findprime", 1, __LINE__);
if (pmax.status == E_LINT_INV) LINT::panic (E_LINT_VAL, "findprime", 2, __LINE__);
if (pmin > pmax) LINT::panic (E_LINT_VAL, "findprime", 1, __LINE__);
if (f.status == E_LINT_INV) LINT::panic (E_LINT_VAL, "findprime", 3, __LINE__);
if (f.iseven()) //0<fmust be odd
LINT::panic (E_LINT_VAL, "findprime", 3, __LINE__);
LINT p = randBBS (pmin, pmax);
LINT t = pmax - pmin;
if (p.iseven())
{
++p;
}
if (p > pmax)
{
p=pmin+p%(t+1);
}
while ((gcd (p - 1, f) != 1) || !p.isprime())
{
++p;
++p;
while (p > pmax)
{
p=pmin+p%(t+1);