mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-12-02, 19:01   #1
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2·41 Posts
Default Are these polynomials being generated correctly?

I'm just double checking that the polynomials in my upcoming implementation of the MPQS are being generated correctly:

n = 1287871475892167
First prime is near sqrt(sqrt(2*N)/M), where M is the sieve size, in this case: 500,000

Polynomials generated (Ax + B)^2 - N:
A: 121
B: 109

A: 169
B: 51

A: 361
B: 345

A: 1849
B: 533

A: 2209
B: 1655

A: 2809
B: 2757

This is how I'm generating them:
After finding a prime Q close to sqrt(sqrt(2*N)/M), which is a quadratic residue mod N, I set:
A = Q^2
h = N^((Q+1)/4) mod Q
v = (2h)^-1 * ((N - h^2)/Q) mod Q
B = h + vQ mod Q^2

If B is even, then B = A - B.

In the trial division stage, values of X are plugged into the polynomial (Ax + B)^2 - N, and divided by A, before being divided over the factor base.

Is this process correct? Are the polynomials above correct for the given input?

Thank You

Last fiddled with by Sam Kennedy on 2016-12-02 at 19:02
Sam Kennedy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Externally Generated Polynomials Don't Seem To Be Being Considered EdH Msieve 4 2017-02-03 15:13
mprime (Linux) doesn't do "affinity" correctly... chalsall Software 16 2014-01-03 15:55
LLR not doing checkpoints correctly on some numbers Puzzle-Peter Conjectures 'R Us 0 2013-08-15 13:45
[Win7] GnuPG-generated files not showing up? ixfd64 Lounge 1 2012-06-23 12:43
Running Glucas correctly? Unregistered Software 15 2003-12-14 20:27

All times are UTC. The time now is 19:42.


Thu Aug 18 19:42:25 UTC 2022 up 17:10, 0 users, load averages: 1.67, 1.71, 1.60

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.

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