Factoring with Highly Composite Modulus

mgb · 2006-09-04, 08:13

Any comments on my blog, here-

http://mgb777.spaces.live.com

Click on 'Factoring with Highly Composite Modulus'

mgb · 2006-09-08, 08:19

No comments?

xilman · 2006-09-08, 12:38

Quote:

Originally Posted by mgb

No comments?

None from me up to now because I went there and saw nothing I recognized as being new. Fermat himself knew all that stuff and exploited it to speed up his computations.

Summary: nothing wrong with what you say, but it's been well documented now fow well over 300 years.

Paul

mgb · 2006-09-09, 10:35

Yes, but what I'm wondering is whether the Quadratic Residues and their differences can be calculated without trial and error.

One solution is x = (r + 1)/2 and y = (r - 1)/2 so that x and y are the roots of the pair of Quadratic Residues which, by their difference, give a particular r.

So the question is, given one pair, can we derive the other pairs from it?

Suppose Xi - Yi = r (mod H) is one pair and Xj - Yj is another, we have

Xi - Xj = Yi - Yj (mod H).

It turns out that if d = Xi - Xj, d is a divisor of H or a multiple of a divisor of H and all other Xx - Xy are d or multiples of d. So, there is a distinct pattern.

If the other pairs can be derived from this given pair, finding Y^2 is easy as even large values of H have a very small number of pairs to test. This is my point. For example-

H = 277200
r = 128771
Number of Quadratic Residues = 4224

131796 - 3025 = 128771
159300 - 30529 = 128771
171396 - 42625 = 128771
182196 - 53425 = 128771
220500 - 91729 = 128771
221796 - 93025 = 128771
260100 - 131329 = 128771
270900 - 142129 = 128771
30996 - 179425 = -148429
33300 - 181729 = -148429
70596 - 219025 = -148429
119700 - 268129 = -148429

So with H = 277200 only 12 pairs have to be tested.

2006-09-04, 08:13	#1
mgb "Michael" Aug 2006 Usually at home 2²·3·7 Posts	Factoring with Highly Composite Modulus Any comments on my blog, here- http://mgb777.spaces.live.com Click on 'Factoring with Highly Composite Modulus'

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Highly composite polynomials.	Arkadiusz	Math	5	2012-02-27 14:11
Mersenne primes have highly composite p-1?	ATH	Math	3	2009-06-15 13:11
efficient generation of highly non-primitive roots	vector	Math	7	2007-11-14 16:07
Factoring non-form composite	roger	Factoring	15	2006-11-29 08:58
Factoring highly composite Mersenne numbers	philmoore	Factoring	21	2004-11-18 20:00

2006-09-08, 08:19	#2
mgb "Michael" Aug 2006 Usually at home 84₁₀ Posts	No comments?

2006-09-09, 10:35	#4
mgb "Michael" Aug 2006 Usually at home 2²×3×7 Posts	Yes, but what I'm wondering is whether the Quadratic Residues and their differences can be calculated without trial and error. One solution is x = (r + 1)/2 and y = (r - 1)/2 so that x and y are the roots of the pair of Quadratic Residues which, by their difference, give a particular r. So the question is, given one pair, can we derive the other pairs from it? Suppose Xi - Yi = r (mod H) is one pair and Xj - Yj is another, we have Xi - Xj = Yi - Yj (mod H). It turns out that if d = Xi - Xj, d is a divisor of H or a multiple of a divisor of H and all other Xx - Xy are d or multiples of d. So, there is a distinct pattern. If the other pairs can be derived from this given pair, finding Y^2 is easy as even large values of H have a very small number of pairs to test. This is my point. For example- H = 277200 r = 128771 Number of Quadratic Residues = 4224 131796 - 3025 = 128771 159300 - 30529 = 128771 171396 - 42625 = 128771 182196 - 53425 = 128771 220500 - 91729 = 128771 221796 - 93025 = 128771 260100 - 131329 = 128771 270900 - 142129 = 128771 30996 - 179425 = -148429 33300 - 181729 = -148429 70596 - 219025 = -148429 119700 - 268129 = -148429 So with H = 277200 only 12 pairs have to be tested.