2 questions about numbers

mhill

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) ??

HallsofIvy

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!

mhill

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

CRGreathouse

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!

mhill

i think that the sum over [tex] \nu [/tex] can be evaluated exactly , so the expression becomes a simple sum over 'mu'

CRGreathouse

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.