Loading ...
Sorry, an error occurred while loading the content.

The complexity of p-1 factoring again

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... 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
    • 0 Attachment
      -----BEGIN PGP SIGNED MESSAGE-----
      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 (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.