mersenneforum.org > Math Mersenne-version of the quadratic sieve
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2008-09-19, 00:43 #1 Syd     Sep 2008 Krefeld, Germany 111001102 Posts Mersenne-version of the quadratic sieve Hi everyone, i tried to modify the quadratic sieve for mersenne primes, can anyone please comment on this one? All factors of mersenne numbers have the form (k*x+1), for x being the exponent. So: 2^x-1 = ((k+t)*x+1)((k-t)*x+1) 2^x-1 = k^2*x^2 - t^2*x^2 + 2kx + 1 k^2*x + 2kx - (2^x-2)/x = t^2*x now we need a k to make the left side positive and start with k=(sqrt(2^x-1)-1)/x and go up from that until the left side is divisible by x (any way to improve that?) When found, we increase k by x in the next steps and get a divisable one every step. Divise all them by x and continue: Factorize all numbers found that way and cut out double prime factors, multiply all remaining factors and put that number in a big list. Check every new number coming in against all the others on the list in that way: is new*old/ggt(new,old)^2 < new? Then add new to the list. x*y/ggt(x,y)^2 wipes out all common prime factors. If we finally get a zero we have a factor. Will this algorithm work fast? Will it even work? Thanks for reading

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 5 2016-03-31 06:21 Sam Kennedy Factoring 20 2013-01-09 16:50 Random Poster Factoring 4 2010-02-12 03:09 ThiloHarich Factoring 47 2007-01-08 14:12 ThiloHarich Factoring 5 2006-07-14 09:51

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

Mon Sep 25 23:01:54 UTC 2023 up 12 days, 20:44, 0 users, load averages: 1.42, 1.18, 1.07

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔