1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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]

    http://en.wikipedia.org/wiki/Divisor_function
     
  5. May 3, 2008 #4

    CRGreathouse

    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

    CRGreathouse

    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
    [tex]O\left(2^{n^{1/3+\varepsilon}}\right)[/itex]
    of GNFS.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: 2 questions about numbers
  1. A question about SU(2) (Replies: 4)

Loading...