mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   On crt based factorization? (https://www.mersenneforum.org/showthread.php?t=19247)

 Unabomber 2014-04-04 19:20

On crt based factorization?

It is bothering my why I have never read ideas on this, not a single word. Eventhough it may be due to my unknowledge on this subject. If I am wasting time of forum goers, please forgive me.

Any odd integer x in can be presented in the form x = a^2 - b^2. Being so, there must be quadratic residues d and e modulo n, a = d - e, where a is remainder of x modulo n ,and n arbitrary integer number.

There are various, and really various, numbers n and residues, where this condition is meat only once. Solution in unique.

For example, if number to be factorized is of the form 8n+1, then a must be of form 8n+1 and b of the form 8n. Like numbers 3*11 = 7^2-8^2 are.

How fast can factorization be, using these facts and chinese remainder theorem?

If the amount of these solutions is small and modulo is large, a large amount of factors is outsieved. Could this be useful?

 R.D. Silverman 2014-04-04 20:19

[QUOTE=Unabomber;370315]It is bothering my why I have never read ideas on this, not a single word. Eventhough it may be due to my unknowledge on this subject. If I am wasting time of forum goers, please forgive me.

Any odd integer x in can be presented in the form x = a^2 - b^2. Being so, there must be quadratic residues d and e modulo n, a = d - e, where a is remainder of x modulo n ,and n arbitrary integer number.

<snip>

[/QUOTE]

I will be generous and assume that the post is just poorly written.

Factoring x by difference of squares with exclusion moduli (which is what
you are discussing, if in a confused way) is strictly an exponential time
algorithm. --> worthless for numbers of any moderate (e.g. 25+ digits)
size.

 All times are UTC. The time now is 04:29.