mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)

 Citrix 2004-06-25 23:20

P-1

Just need some clarification,

Is this quote wrong.

"There is an enhancement to Pollard's algorithm called stage 2 that uses a second bound, B2. Stage 2 will find the factor q if k has [B]just one [/B] factor between B1 and B2 and all remaining factors are below B1."

Taken from

[url]http://www.mersenne.org/math.htm[/url]

Let me know!

Thanks,
Citrix
:cool: :cool: :cool:

 Axel Fox 2004-06-26 03:12

First stage only uses B1 and all factors of k have to be below B1.
Stage two is a little more general and allows for 1 of the factors of k to be above B1, but still below a second bound (B2).

Greets,
Axel Fox.

 Citrix 2004-06-26 03:38

Why can't there be 2 k's between b1 and b2? I think there can be 2 or more k's.

Citrix
:cool: :cool: :cool:

 Citrix 2004-06-26 03:58

[QUOTE=Citrix]Why can't there be 2 k's between b1 and b2? I think there can be 2 or more k's.[/QUOTE]

146420587 |79309*2^513-1

Found this uisng a program I wrote.
b1=25 and b2=1000.

I think this prooves my point.

Citrix
:cool: :cool: :cool:

 axn 2004-06-26 04:51

Can you post your program here?

 Citrix 2004-06-26 05:01

Here you go.
It is very basic.
The routines are primitive etc.
Don't try very large numbers.

The file is 183 KB, it won't let me upload it. If you PM me your email, I can send it to you or better yet I can test and print the results for you.

Citrix
:cool: :cool: :cool:

 akruppa 2004-06-26 06:49

There are at least three effects how P-1 can occasionally find factors that are not B1,B2 smooth. Say [I]p[/I]-1 has two factors >B1, [I]r[/I] and [I]s[/I].

- The starting element of P-1 could already be an [I]r[/I]-th or [I]s[/I]-th power (mod [I]p[/I]). Then there is no need to exponentiate by [I]r[/I] for P-1 to find [I]p[/I]. The probability of a random residue being an [I]r[/I]-th power (mod [I]p[/I]) is 1/[I]r[/I] if [I]r[/I]|[I]p[/I]-1 so this wont happen often for large [I]r[/I]. For example, the smallest starting values that are a 127-th power (mod 146420587) are 89, 149, 219, 554...

- The implementation of P-1 might exponentiate by [I]N[/I]-1 at the start of stage 1. This is useful if there is some [I]k[/I] that divides [I]p[/I]-1 for every prime factor [I]p[/I] of [I]N[/I] because is includes [I]k[/I] as a stage 1 exponent, without having to know what the actual value of [I]k[/I] is. But this is not what happened here, neither 127 nor 379 divide 79309*2^513-2.

- The [I]r[/I] and [I]s[/I] may be included by the Brent-Suyama extension. If [I]t[/I] is the order of the end-of-stage-1 residue, the factor [I]p[/I] will be found if [I]t[/I]|[I]f[/I]([I]l[/I])-[I]f[/I]([I]m[/I]). Here [I]f[/I]() is the Brent-Suyama function (usually just a power) and [I]l[/I] and [I]m[/I] are usually chosen so that all primes >B1, <=B2 are included. It's possible that a composite [I]t[/I] divides one such value, but is again not too likely to happen. Whether that's why the factor was found requires knowing which function [I]f[/I]() the implenentation uses and how it generates the [I]l[/I] and [I]m[/I] values.

Alex

 Citrix 2004-06-26 06:53