Efficient Computation of Congruence Solutions and Generating Functions

[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

n=p.q and \sigma _{1} (n)=1+p+q+n

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 f(x)=0 mod(p) 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 \sigma_1(n) 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

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

http://en.wikipedia.org/wiki/Divisor_function

 

[CRGreathouse]

Factoring by trial division takes at most \sqrt n divisions (or at most 2+\sqrt n/3 divisions with 2, 3, and numbers 1,5 mod 6, or at most \pi(\sqrt n) with a precalculated list of primes), while that double sum takes n^2/2 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 \nu can be evaluated exactly , so the expression becomes a simple sum over 'mu'

 

[CRGreathouse]

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

If you can calculate sum_{\nu=1}^{\mu}\cos\frac{2\pi\nu n}{\mu} in unit time, computing
\sum_{\mu=1}^N\mu^{x-1}\sum_{\nu=1}^{\mu}\cos\frac{2\pi\nu N}{\mu}
takes time
O(2^n) (with 2^{n-1}\le N<2^n)
which is not nearly competitive with the
O\left(2^{n^{1/3+\varepsilon}}\right)[/itex]<br /> of GNFS.