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:

- $M = B!$
- $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?

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestThe 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.

Log in to reply