mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2014-04-04, 19:20   #1
Unabomber
 
Apr 2014

1 Posts
Default 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?
Unabomber is offline   Reply With Quote
Old 2014-04-04, 20:19   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by Unabomber View Post
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>
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality test based on factorization of n^2+n+1 carpetpool Miscellaneous Math 5 2018-02-05 05:20
Calculating E based on B1 c10ck3r Math 1 2012-02-22 06:29
Is based 10 used for calculations? Googol Information & Answers 2 2007-07-27 03:09
DWT-based calendar ewmayer Puzzles 7 2007-04-19 22:33
Prime95 on NT-based OS ThomRuley Software 2 2004-03-21 15:30

All times are UTC. The time now is 12:23.

Fri Oct 23 12:23:28 UTC 2020 up 43 days, 9:34, 0 users, load averages: 1.40, 1.43, 1.39

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.