Re: Test for divisors of Phi(N)

From: David Wagner (daw_at_mozart.cs.berkeley.edu)
Date: 08/01/03

  • Next message: Joe Peschel: "Re: Leopard13 contest withdrawal !" 
    Date: Fri, 1 Aug 2003 21:01:13 +0000 (UTC)

    AMMS716 wrote:
    >Suppose we had a test which, given N and
    >d returned phi(N) mod d. Such a test can
    >be used to quickly factor N. phi(N) can
    >be reconstructed by the CRT if we have
    >phi(N) mod d_i for sufficiently many d_i
    >such that prod(d_i) > phi(N).

    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?

  • Next message: Joe Peschel: "Re: Leopard13 contest withdrawal !"

    Relevant Pages

    • Re: Test for divisors of Phi(N)
      ... I believe the original poster asked about ... > checking divisibility rather than computing phimod d. ... One can think of other ways to attack N. For instance, if 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)