mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-09-04, 08:13   #1
mgb
 
"Michael"
Aug 2006
Usually at home

22·3·7 Posts
Default Factoring with Highly Composite Modulus

Any comments on my blog, here-

http://mgb777.spaces.live.com

Click on 'Factoring with Highly Composite Modulus'
mgb is offline   Reply With Quote
Old 2006-09-08, 08:19   #2
mgb
 
"Michael"
Aug 2006
Usually at home

8410 Posts
Default

No comments?
mgb is offline   Reply With Quote
Old 2006-09-08, 12:38   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

101101100001102 Posts
Default

Quote:
Originally Posted by mgb View Post
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
xilman is offline   Reply With Quote
Old 2006-09-09, 10:35   #4
mgb
 
"Michael"
Aug 2006
Usually at home

22×3×7 Posts
Default

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.
mgb is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 10:43.


Tue Jan 31 10:43:09 UTC 2023 up 166 days, 8:11, 0 users, load averages: 1.78, 1.11, 1.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”