Skip to main content
Cryptography

Timeline for Sieving the sequence $x^2-n$ to recognize b-smooth numbers

Current License: CC BY-SA 3.0

14 events
when toggle format what by license comment
Apr 13, 2017 at 12:48 history edited CommunityBot
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
May 30, 2016 at 5:48 history edited fgrieu♦ CC BY-SA 3.0
Polish
May 30, 2016 at 5:47 comment added fgrieu♦ @Burak: Practical high-performance implementations, and most references with that aim, sieve numbers of the forms $(a\cdot x+b)^2−n$ for various $(a,b)$, rather than $x^2-k\cdot n$ for various $k$ as reference [1] does. If you only sieve $x^2-n$ for $x$ starting at $\lceil\sqrt n\rceil$, then depending on the size of the factor base you'll get a factorization before $x$ reaches $\lceil\sqrt{2n}\rceil$, after that, or never.
May 30, 2016 at 5:31 history edited fgrieu♦ CC BY-SA 3.0
Polish
May 30, 2016 at 5:24 history edited fgrieu♦ CC BY-SA 3.0
De-emphasize $k$
May 30, 2016 at 5:16 history edited fgrieu♦ CC BY-SA 3.0
Polish
May 30, 2016 at 5:10 history edited fgrieu♦ CC BY-SA 3.0
Explain what MPQS actually does
May 28, 2016 at 15:21 vote accept Burak
May 28, 2016 at 11:55 history edited fgrieu♦ CC BY-SA 3.0
Polish
May 28, 2016 at 11:35 history edited fgrieu♦ CC BY-SA 3.0
Expand
May 27, 2016 at 19:09 history edited fgrieu♦ CC BY-SA 3.0
Addition
May 27, 2016 at 11:54 comment added Burak I find it really strange that this is not mentioned in the references. If I don't look at $x^2 - k*n$ I would never get the correct factorization, wouldn't I? The abort point for x is when $x \geq \sqrt{2n}$? I also get another factor base for $2n$? It makes the whole procedure much more complicated than it look liked.
May 27, 2016 at 4:43 history edited fgrieu♦ CC BY-SA 3.0
Notice that k could be computed, but is not.
May 27, 2016 at 4:30 history answered fgrieu♦ CC BY-SA 3.0