view release on metacpan or  search on metacpan

docs/1-Fast_Generation_Of_Primes-Ueli_Maurer.ps  view on Meta::CPAN

Ft(i)1244 994 y FE(=)p Fl(sl[i])p FE(,)e(the)h(actual)g(appro)o(xi-)35
1053 y(mate)e(size)h Fy(Q)d Fu(\031)h Fy(P)364 1036 y
Ft(s)380 1041 y Fs(i)410 1053 y FE(is)i(computed)f(b)o(y)g(the)g
(statemen)o(t)f Fl(Q)24 b(:=)f(Exponentiate\(P,sl[i]\))p
FE(.)17 b(Here)d Fy(Q)35 1112 y FE(is)g(tak)o(en)f(as)g(the)g
(geometric)h(midp)q(oin)o(t)g(of)f(an)g(in)o(terv)m(al)h([)p
Fy(Q=c)1094 1124 y Fh(in)o(t)1146 1112 y Fy(;)8 b(Q)e
Fu(\001)g Fy(c)1248 1124 y Fh(in)o(t)1299 1112 y FE(])13
b(where)h Fy(c)1475 1124 y Fh(in)o(t)1540 1112 y Fy(>)f
FE(1)g(is)g(a)g(small)35 1172 y(constan)o(t)h(\(e.g.,)g
Fy(c)352 1184 y Fh(in)o(t)416 1172 y FE(=)f(1)p Fy(:)p
FE(2\).)19 b(Then)c(a)f(prime)i(is)f(selected)h(\(appro)o(ximately\))e
(at)g(random)h(from)f(this)35 1231 y(in)o(terv)m(al)j(b)o(y)e(recursiv)
o(e)h(application)h(of)d(the)i(pro)q(cedure)g Fl(RandomPrime)p
FE(.)106 1302 y(After)j Fy(F)25 b FE(=)337 1270 y Fp(Q)376
1283 y Ft(r)376 1313 y(i)p FB(=1)443 1302 y Fy(q)463
1309 y Ft(i)496 1302 y FE(is)20 b(generated,)f(in)o(tegers)g
Fy(R)g FE(are)g(c)o(hosen)g(at)f(random)h(with)g(uniform)g(dis-)35
1361 y(tribution)i(from)d(the)h(in)o(terv)m(al)i([)p
Fy(I)627 1368 y FB(1)646 1361 y Fy(;)8 b(I)687 1368 y
FB(2)706 1361 y FE(],)19 b(where)h Fy(I)907 1368 y FB(1)946
1361 y FE(=)g(\()p Fy(P)1048 1368 y FB(1)1080 1361 y
Fu(\000)13 b FE(1\))p Fy(=)p FE(\(2)p Fy(F)6 b FE(\))18
b(and)h Fy(I)1416 1368 y FB(2)1455 1361 y FE(=)h(\()p
Fy(P)1557 1368 y FB(2)1590 1361 y Fu(\000)13 b FE(1\))p
Fy(=)p FE(\(2)p Fy(F)6 b FE(\),)35 1420 y(un)o(til)17
b Fy(n)c FE(=)g(2)p Fy(RF)j FE(+)10 b(1)15 b(is)h(prime.)k(Candidates)c
Fy(n)f FE(are)g(tested)g(\014rst)g(b)o(y)g(trial)h(division)h(up)f(to)e
(a)h(b)q(ound)35 1480 y(determined)f(b)o(y)f(the)g(pro)q(cedure)g
Fl(g)p 639 1487 24 2 v 24 w(opt)f FE(and)h(then)g(b)o(y)g(the)g(pro)q
(cedure)g Fl(CheckLemma1)e FE(whic)o(h)j(c)o(hec)o(ks)35
1539 y(whether)i(the)f(conditions)i(of)d(Lemma)i(1)e(for)h(primalit)o
(y)h(of)f Fy(n)g FE(are)g(satis\014ed.)35 1693 y Fn(3.3.)25
b(Implem)o(en)n(tation)15 b(issues)k(and)g(further)f(commen)n(ts)106
1799 y FE(The)e(describ)q(ed)i(implemen)o(tation)f(of)e
Fl(RandomPrime)f FE(assumes)i(that)f(the)h(spread)f Fy(P)1584
1806 y FB(2)1604 1799 y Fy(=P)1656 1806 y FB(1)1692 1799
y FE(of)g(the)35 1859 y(in)o(terv)m(al)23 b([)p Fy(P)248
1866 y FB(1)268 1859 y Fy(;)8 b(P)318 1866 y FB(2)337
1859 y FE(])21 b(is)i(reasonably)f(small)h(\(e.g.,)f(less)g(than)g
(2\).)39 b(If)22 b(a)g(prime)g(should)h(b)q(e)g(selected)35
1918 y(uniformly)e(from)f(a)f(larger)h(in)o(terv)m(al,)i(it)e(is)h
(advisable)g(to)e(cut)h(the)g(in)o(terv)m(al)h(in)o(to)f(subin)o(terv)m
(als)h(of)35 1977 y(reasonable)14 b(spread,)g(to)f(select)h(one)g(of)f
(the)h(in)o(terv)m(als)g(at)f(random)g(according)h(to)f(the)h(corresp)q
(onding)35 2036 y(probabilit)o(y)g(distribution,)h(and)e(to)f(use)h
(the)g(pro)q(cedure)h Fl(RandomPrime)d FE(to)h(generate)g(a)h(prime)g
(in)h(the)35 2096 y(selected)j(in)o(terv)m(al.)106 2167
y(A)d(problem)h(with)g(the)g(pro)q(cedure)g Fl(RandomPrime)e
FE(as)h(describ)q(ed)i(ab)q(o)o(v)o(e)e(is)h(that)e(when)i(the)g(rela-)
35 2226 y(tiv)o(e)f(size)f(1)6 b Fu(\000)275 2194 y Fp(P)319
2207 y Ft(r)319 2238 y(i)p FB(=1)385 2226 y Fy(s)406
2233 y Ft(i)434 2226 y FE(of)12 b Fy(R)h FE(is)g(to)q(o)g(small,)h
(then)f(the)g(in)o(terv)m(al)h([)p Fy(I)1154 2233 y FB(1)1173
2226 y Fy(;)8 b(I)1214 2233 y FB(2)1233 2226 y FE(])13
b(ma)o(y)f(b)q(e)i(to)q(o)e(small)i(to)e(con)o(tain)35
2285 y(an)i Fy(R)g FE(for)f(whic)o(h)i(2)p Fy(RF)f FE(+)8
b(1)13 b(is)i(prime.)20 b(An)14 b(endless)h(execution)g(of)f(the)g
Fl(WHILE)f FE(lo)q(op)h(can)g(b)q(e)h(prev)o(en)o(t-)35
2345 y(ed,)h(for)f(example)i(b)o(y)f(restricting)g(the)g(n)o(um)o(b)q
(er)g(of)f(iterations.)21 b(F)l(urthermore,)15 b(it)h(m)o(ust)f(b)q(e)i
(a)o(v)o(oided)35 2404 y(with)c(high)h(probabilit)o(y)f(that)f(the)h
(in)o(terv)m(al)g([)p Fy(I)830 2411 y FB(1)850 2404 y
Fy(;)8 b(I)891 2411 y FB(2)909 2404 y FE(])13 b(con)o(tains)f(no)h
(prime)g(factor)e(b)q(ecause)j(in)f(this)g(case)35 2463
y Fy(F)26 b FE(\(or)18 b(at)g(least)h(the)g(smallest)g(prime)h(factor)d
(of)i Fy(F)6 b FE(\))19 b(w)o(ould)g(ha)o(v)o(e)f(to)h(b)q(e)g
(regenerated.)31 b(Allo)o(wing)35 2522 y Fy(F)25 b FE(to)17
b(b)q(e)i(rejected)f(with)g(non-negligibl)q(e)j(probabilit)o(y)e(w)o
(ould)f(increase)h(the)f(running)h(time)f(of)g(the)899
2699 y(11)p eop
%%Page: 12 12
12 11 bop 35 140 a FE(algorithm)13 b(signi\014can)o(tly)l(,)h(in)f
(particular)f(b)q(ecause)h(the)f(rejection)h(could)g(happ)q(en)g(at)f
(sev)o(eral)g(lev)o(els)h(of)35 199 y(the)k(recursion.)24
b(W)l(e)17 b(therefore)f(recommend)g(t)o(w)o(o)f(mo)q(di\014cation)j
(to)e(the)g(pro)q(cedure)i Fl(RandomPrime)35 259 y FE(whic)o(h)e(are)f
(not)g(describ)q(ed)i(in)f(Figure)g(1.)83 347 y(1.)k(The)15
b(output)g(of)f(the)h(pro)q(cedure)g Fl(GenerateSizeList)e
FE(should)i(only)g(b)q(e)h(accepted)f(if)g(the)g(sum)139
407 y(of)21 b(the)g(relativ)o(e)g(sizes,)i(1)13 b Fu(\000)657
374 y Fp(P)701 388 y Ft(r)701 418 y(i)p FB(=1)768 407
y Fy(s)789 414 y Ft(i)803 407 y FE(,)22 b(is)g(less)f(than)g(a)f(giv)o
(en)i(b)q(ound.)37 b(W)l(e)21 b(suggest)g(to)f(use)139
466 y(the)j(b)q(ound)h(1)14 b Fu(\000)i Fy(C)494 473
y FB(1)513 466 y Fy(=)p FE(\(log)612 477 y FB(2)639 466
y Fy(P)22 b FE(+)15 b Fy(C)773 473 y FB(2)793 466 y FE(\))22
b(for)g Fy(C)943 473 y FB(1)987 466 y Fu(\031)j FE(10)e(and)f
Fy(C)1244 473 y FB(2)1289 466 y Fu(\031)j FE(50.)42 b(This)23
b(mo)q(di\014cation)139 525 y(reduces)18 b(the)f(div)o(ersit)o(y)g(of)f
(reac)o(hable)i(primes)f(sligh)o(tly;)i(ho)o(w)o(ev)o(er,)d(this)h(can)
g(b)q(e)h(tolerated)e(in)139 584 y(applications.)30 b(In)19
b(particular,)g(primes)g Fy(p)f FE(for)g(whic)o(h)h(\()p
Fy(p)11 b Fu(\000)i FE(1\))p Fy(=)p FE(2)j(is)j(the)f(pro)q(duct)h(of)e
(a)h(small)139 644 y Fy(R)g FE(and)g(a)f(prime)i(or)e(the)h(pro)q(duct)
g(of)f(a)h(small)g Fy(R)g FE(and)g(t)o(w)o(o)f(primes)h(of)f(similar)i
(size,)g(cannot)139 703 y(b)q(e)g(reac)o(hed.)29 b(These)18
b(unreac)o(hable)h(primes)g(include)i(the)d(primes)g(often)g(referred)g
(to)g(as)f FD(safe)139 762 y FE(primes,)i(an)f(attribute)g(not)g
(justi\014ed)h(su\016cien)o(tly)g(in)g(the)f(author's)f(opinion)j(b)q
(ecause)f(there)139 821 y(exist)e(no)f(indications)j(that)c(these)i
(primes)g(lead)g(to)f(the)g(most)g(di\016cult)i(factoring)e(instances.)
139 881 y(It)g(is)g(ev)o(en)g(conceiv)m(able,)i(though)e(not)f(lik)o
(ely)l(,)i(that)e(the)h(so-called)h(safe)f(primes)g(form)f(a)g(small)
139 940 y(class)j(of)g(primes)h(that)e(are)g(actually)i(insecure.)29
b(Discarding)19 b(these)f(sp)q(ecial)i(primes)e(distorts)139
999 y(the)i(uniformit)o(y)h(of)e(the)h(distribution)i(sligh)o(tly)l(,)g
(but)e(has)g(essen)o(tially)i(no)e(in\015uence)i(on)e(the)139
1059 y(securit)o(y)c(of)f(a)f(cryptographic)i(sc)o(heme.)83
1147 y(2.)k(It)c(is)g(further)f(recommended)h(to)f(let)h(the)f(in)o
(terv)m(al)h(constan)o(t)f Fy(c)1244 1159 y Fh(in)o(t)1312
1147 y FE(dep)q(end)i(on)e Fy(P)1562 1154 y FB(2)1582
1147 y FE(,)g(increasing)139 1207 y(when)f Fy(P)285 1214
y FB(2)318 1207 y FE(decreases,)f(to)f(ensure)i(that)e(the)i(spread)f
(of)f(the)h(in)o(terv)m(als)h(passed)g(to)e(the)h(pro)q(cedure)139
1266 y Fl(RandomPrime)18 b FE(is)i(alw)o(a)o(ys)f(su\016cien)o(tly)i
(large)e(to)g(guaran)o(tee)g(that)g(for)g(the)g(largest)g(p)q(ossible)
139 1325 y(v)m(alue)i(1)12 b Fu(\000)h Fy(C)377 1332
y FB(1)397 1325 y Fy(=)p FE(\(log)496 1336 y FB(2)523
1325 y Fy(P)19 b FE(+)14 b Fy(C)653 1332 y FB(2)672 1325
y FE(\))19 b(for)f(the)i(sum)f(1)12 b Fu(\000)1049 1293