Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.8k
Update factorization.md [Update Powersmooth Definition]#1461
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:main
Are you sure you want to change the base?
Uh oh!
There was an error while loading.Please reload this page.
Conversation
The definition of powersmooth was a bit confusing so I added a formal definition inspired by a number theory book.
Hi, thank you very much for the pull request! I think one other issue here is that the article mistakenly applies the term "powersmooth" to On a side note, I think it's more common to put commas outside of |
t0wbo2t commentedMay 21, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Sure, done. |
Commas are now outside $...$ and definiton is for (p - 1) for consistency.
Thanks! But what I meant is, the article currently uses an incorrect definition of powersmooth, and your initial edit was correct. And I suggested to rewrite other parts of the article to make it clear that the powersmooth number is actually |
Updated materials related to powersmoothness.Corrected some minor mistakes.
I have changed materials to the best of my knowledge. Please let me know if there are any errors. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Thanks for the update! I added a few more change suggestions, hopefully after that situation about powersmooth numbers will be completely clarified.
| @@ -189,11 +188,11 @@ Notice, if $p-1$ divides $M$ for all prime factors $p$ of $n$, then $\gcd(a^M - | |||
| In this case we don't receive a factor. | |||
| Therefore, we will try to perform the $\gcd$ multiple times, while we compute $M$. | |||
| Some composite numbers don't have $B$-powersmooth factors for small $B$. | |||
| Some composite numbers don't have $\mathrm{B}$-powersmooth factors for small $\mathrm{B}$. | |||
| For example, the factors of the composite number $100~000~000~000~000~493 = 763~013 \cdot 131~059~365~961$ are $190~753$-powersmooth and $1~092~161~383$-powersmooth. | |||
| We will have to choose $B >= 190~753$ to factorize the number. | |||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| We will have to choose $B>= 190~753$ to factorize the number. | |
| We will have to choose $B\geq 190~753$ to factorize the number. |
| Some composite numbers don't have $\mathrm{B}$-powersmooth factors for small $\mathrm{B}$. | ||
| For example, the factors of the composite number $100~000~000~000~000~493 = 763~013 \cdot 131~059~365~961$ are $190~753$-powersmooth and $1~092~161~383$-powersmooth. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| Some composite numbers don't have$\mathrm{B}$-powersmooth factors for small $\mathrm{B}$. | |
| For example,the factors ofthe composite number $100~000~000~000~000~493 = 763~013 \cdot 131~059~365~961$are $190~753$-powersmooth and $1~092~161~383$-powersmooth. | |
| Some composite numbers don't havefactors $p$ s.t. $p-1$ is $\mathrm{B}$-powersmooth for small $\mathrm{B}$. | |
| For example,forthe composite number $100~000~000~000~000~493 = 763~013 \cdot 131~059~365~961$, values $p-1$are $190~753$-powersmooth and $1~092~161~383$-powersmooth correspondingly. |
| And thefactorsare $31$-powersmooth and $16$-powersmoothrespectably, because $1303 - 1 = 2 \cdot 3 \cdot 7 \cdot 31$ and $3697 - 1 = 2^4 \cdot 3 \cdot 7 \cdot 11$. | ||
| In 1974 John Pollard invented a method to extracts $B$-powersmooth factors from a composite number. | ||
| And thevalues, $1303 - 1$ and $3697 - 1$,are $31$-powersmooth and $16$-powersmoothrespectively, because $1303 - 1 = 2 \cdot 3 \cdot 7 \cdot 31$ and $3697 - 1 = 2^4 \cdot 3 \cdot 7 \cdot 11$. | ||
| In 1974 John Pollard invented a method to extracts $\mathrm{B}$-powersmooth factors from a composite number. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| In 1974 John Pollard invented a method toextracts $\mathrm{B}$-powersmooth factors from a composite number. | |
| In 1974 John Pollard invented a method toextract factors $p$, s.t. $p-1$ is $\mathrm{B}$-powersmooth, from a composite number. |
The definition of powersmooth was a bit confusing so I added a formal definition inspired by a number theory book.