Re: Test for divisors of Phi(N)

From: Marcel Martin (mm_at_ellipsa.net)
Date: 08/02/03 

Date: Sat, 02 Aug 2003 01:48:07 +0200

David Wagner a écrit :
> I'm not sure I understand. I believe the original poster asked about
> checking divisibility rather than computing phi(N) mod d.
>
> Suppose we had a test which, given N and d returned whether d divides
> phi(N). Then I believe there is no known way to use this to factor N.
>
> Did I miss something?

If you could collect enough D_i's, you could apply Silverman's idea
with phi(N) = 0 mod D_i.

One can think of other ways to attack N. For instance, if D divides
phi(N), there are elements of order D in Z/NZ. Collect enough D_i's
and try to find
a^(D_i*D_j*...*D_z) = 1 mod N
b^(D_i*D_j*...*D_z) = 1 mod N (with 1 < a < b)
then find some factors F_i's of
a^(D_i*D_j*...*D_z) - b^(D_i*D_j*...*D_z)
and look if gcd(F_i, N) gives a factor of N.
This works well with Carmichael numbers, but with them, it is not
difficult to find values a, b and k such that a^k = b^k = 1 :-)

Marcel Martin

Relevant Pages

  • Re: Test for divisors of Phi(N)
    ... I believe the original poster asked about ... checking divisibility rather than computing phimod d. ... Suppose we had a test which, given N and d returned whether d divides ...
    (sci.crypt)
  • Re: A Formula for Pi
    ... alternating series. ... rule out R because of its sqrtmultiplier. ... computing one term of R is as expensive as computing several ... No divides. ...
    (sci.math)
  • Re: some number theory problem
    ... divisibility arguments very quickly reduces the problem. ... by saing 'minimal rational form' you mean x=p/q for which GCD=1? ... prime, we conclude that q divides a and a divides q, so a = q. ... the fact that p and q are relatively prime, we conclude that p and q ...
    (sci.math)
  • Re: New paper, algebraic integers, Galois Theory
    ... > such that p divides xy in S. Then in R, p divides x or p divides y, ... i.e. divisibility in R, when restricted to S, is the ... remains true when restricted down into substructures. ... of relational structures. ...
    (sci.math)
  • Re: Request for Comments [suggestions, queries, etc] w.r.t LibTomMath
    ... this means that 0 divides 0. ... ordering imposed by divisibility, not with respect to normal integer ... this has the unfortunate consequence of making the GCD ...
    (sci.crypt)