## The complexity of p-1 factoring again

Expand Messages
• ... Hash: SHA1 Rehashing the old thread... What I had found out until then was that the cost of a first stage p-1 run on a number n with a bound B was log
Message 1 of 1 , Jan 26, 2003
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

What I had found out until then was that the cost of a first stage p-1 run on
a number n with a bound B was log (B^2/log B) modulo-n multiplications.
However, I didn't know how to choose B back then.

Now I was reading the section on complexity analysis of QS in C&P, and I tried
to apply the same ideas here. Namely, the probability that p-1 is B-smooth is
given by u^(-u), where u = (log B)/(log p-1). So 1/prob(p-1 is B-smooth) =
u^u.

My next step would be trying to minimize the expression C = cost(p-1 run with
a given value of B)*1/prob(p-1 is B-smooth) = (u^u)*log(B^2/log B)*M(n),
where M(n) is the cost to do a modular multiplication on two numbers the size
of n. Minimizing the expression would consist of taking dC/dB = 0.

The reasoning here is to consider how the expression C changes with B. As B
grows, the cost term grows and the 1/probability term shrinks. As B shrinks,
the cost term shrinks and the 1/probability term grows. If B is too high,
cost is much higher than 1/probability and C is high too. If B is too low,
1/probability is much higher than cost and C is high as well. So we're
looking for a value with a reasonable cost and a reasonable value of
1/probability too, thus minimizing C overall.

I would like to hear from you guys whether what I said makes sense.

Thanks,

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+NAENce3VljctsGsRAv4YAJ98kKtwSAHKMjKe4dr9tOAPwJ5lqgCff3fn
KcE82SZcnFYy2Ow0pe1Sm+o=
=haAk
-----END PGP SIGNATURE-----
Your message has been successfully submitted and would be delivered to recipients shortly.