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
[tex]O\left(2^{n^{1/3+\varepsilon}}\right)[/itex]
of GNFS.