×

Help: Pollard's p-1, correct way to build M

I need some help regarding one of the steps in Pollard's p-1.

What I understood: We are assuming that there exists $$p$$, a prime factor of $$n$$, such that $$p-1$$ is $$B$$-powersmooth for some $$B$$ (not $$B$$-smooth!) and that we're trying to build a number $$M$$ (to be used as an exponent) such that $$(p-1)|M$$. Most commonly this is done in two ways:

1. $$M = B!$$
2. $$M = \prod {q^a}$$, for all primes $$q <= B$$ and $$a$$ sufficiently large.

Let's focus on the second. My confusion comes from the value of a. Using the main assumption we made ($$p-1$$ is $$B$$-powersmooth) it seems clear that $$a = \lfloor log_q{B} \rfloor$$. However, some sources (including Wikipedia) use $$a = \lfloor log_q{n} \rfloor$$. Since we can assume $$n >> B$$ this works too but makes $$a$$ unnecessarily large.

At first I thought it's just an error on Wikipedia and I made a correction, but I found several revisions in page history that change this both ways ($$B$$ to $$n$$ and back), with no real discussion, which makes me unsure. Can someone explain why $$n$$ makes more sense than $$B$$ here, or confirm that $$n$$ was just an error?

Note by Nikola Jovanović
4 weeks, 1 day ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

The confusion seems to be whether we're assuming $$p-1$$ is $$B$$-powersmooth or $$B$$-smooth, right? If it's $$B$$-powersmooth, then we can use the smaller bound, but if it's $$B$$-smooth, then we have to use the larger one.

The Wikipedia page cites the smaller bound, but the example ($$n=299,$$ $$B=5$$) appears to use the larger bound.

- 3 weeks, 3 days ago