mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-08-15, 08:59   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

3·5·401 Posts
Default Pollard rho with known factor of P-1

Prime Numbers a Computational Perspective by C&P lists as a research problem an extension to pollard rho that finds a factor faster if you know one of the factors of P-1. Would this be helpful for factoring Mersenne numbers as we know a divisor of P-1 or would the cost still be too high?
This is research question 5.24 in http://thales.doa.fmph.uniba.sk/maca...oli/primes.pdf on pages 255 to 256
henryzz is offline   Reply With Quote
Old 2017-08-15, 11:10   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2·5,791 Posts
Default

Quote:
Originally Posted by henryzz View Post
Prime Numbers a Computational Perspective by C&P lists as a research problem an extension to pollard rho that finds a factor faster if you know one of the factors of P-1. Would this be helpful for factoring Mersenne numbers as we know a divisor of P-1 or would the cost still be too high?
This is research question 5.24 in http://thales.doa.fmph.uniba.sk/maca...oli/primes.pdf on pages 255 to 256
My gut feeling is that rho would still be an exponential algorithm with a relatively high power of ln(N) even with the improvements suggested in 5.24 or 5.25. As such, it would be very unlikely to be competitive with ECM.

Added in edit: to clarify, my gut feeling is that modified rho would be uncompetitive with ECM.

Last fiddled with by xilman on 2017-08-15 at 11:33
xilman is offline   Reply With Quote
Old 2017-08-15, 12:13   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

3×5×401 Posts
Default

Quote:
Originally Posted by xilman View Post
My gut feeling is that rho would still be an exponential algorithm with a relatively high power of ln(N) even with the improvements suggested in 5.24 or 5.25. As such, it would be very unlikely to be competitive with ECM.

Added in edit: to clarify, my gut feeling is that modified rho would be uncompetitive with ECM.
I was more thinking in comparison to P-1 which is also an exponential algorithm. The problem is that there is a load of arithmetic that would need doing modulo N. Each iteration would be equivalent in cost to a few LL iterations.
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pollard rho questions Joe O Factoring 9 2016-09-18 15:42
Can Pollard Rho cycles be used to find a factor? wwf Factoring 26 2013-09-30 04:24
Pollard Rho Discrete Log rogue Math 6 2012-09-26 11:20
Efficiency of state-of-the-art Pollard's p-1 fgrieu Software 22 2011-11-25 19:47
Pollard Rho Help? theta Factoring 2 2005-08-23 21:14

All times are UTC. The time now is 22:00.


Mon Dec 5 22:00:32 UTC 2022 up 109 days, 19:29, 0 users, load averages: 0.96, 0.95, 0.84

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

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