Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

2 questions about numbers

  1. Apr 27, 2008 #1
    i would like to solve these 2 problems ..

    let be p and q two primes so n=p.q is known and we must determine the primes p and q is so easy as solving the system

    [tex] n=p.q [/tex] and [tex] \sigma _{1} (n)=1+p+q+n [/tex]

    with 'sigma' the divisor function that gives us the sum of the divisors of a certain number 'n' but is really so easy?

    the second question is given the congruence [tex] f(x)=0 mod(p) [/tex] and N(x) the number of solutions of the congruence above on the interval [0,x] is there a generating function (of any type) to compute N(x) ??
  2. jcsd
  3. Apr 27, 2008 #2


    User Avatar
    Science Advisor

    It's not clear to me what you mean by "so easy". You can't know [itex]\sigma_1(n)[/itex] until you know the factors of n, in which case you already have p and q. In other words, determining the two primes p and q is "just as easy" as factoring n!
  4. Apr 27, 2008 #3
    But according to Wikipedia (here is the apparent paradox) you can compute the divisor function as a double series involving cosine

    [tex] \sigma_x(n)=\sum_{\mu=1}^{n} \mu^{x-1}\sum_{\nu=1}^{\mu}\cos\frac{2\pi\nu n}{\mu} [/tex]

  5. May 3, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper

    Factoring by trial division takes at most [itex]\sqrt n[/itex] divisions (or at most [itex]2+\sqrt n/3[/itex] divisions with 2, 3, and numbers 1,5 mod 6, or at most [itex]\pi(\sqrt n)[/itex] with a precalculated list of primes), while that double sum takes [itex]n^2/2[/itex] trig evaluations. That's a serious slowdown over an already slow method of factoring -- not the mention the roundoff error!
  6. May 7, 2008 #5
    i think that the sum over [tex] \nu [/tex] can be evaluated exactly , so the expression becomes a simple sum over 'mu'
  7. May 7, 2008 #6


    User Avatar
    Science Advisor
    Homework Helper

    If you can calculate [itex]sum_{\nu=1}^{\mu}\cos\frac{2\pi\nu n}{\mu}[/itex] in unit time, computing
    [tex]\sum_{\mu=1}^N\mu^{x-1}\sum_{\nu=1}^{\mu}\cos\frac{2\pi\nu N}{\mu}[/tex]
    takes time
    [tex]O(2^n)[/tex] (with [itex]2^{n-1}\le N<2^n[/itex])
    which is not nearly competitive with the
    of GNFS.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook