Go Back > Great Internet Mersenne Prime Search > Math

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

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

Any comments on my blog, here-

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

8410 Posts

No comments?
mgb is offline   Reply With Quote
Old 2006-09-08, 12:38   #3
xilman's Avatar
May 2003
Down not across

101101100001102 Posts

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.

xilman is offline   Reply With Quote
Old 2006-09-09, 10:35   #4
Aug 2006
Usually at home

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

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.

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