The complexity of p-1 factoring again
- -----BEGIN PGP SIGNED MESSAGE-----
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 (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) =
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.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
-----END PGP SIGNATURE-----