issue encountered:

i'm using yafu 1.10 WIN32 with aliqueit.exe

at n=336756866798891081 factoring the following occurs:

in DOS-window the message

WARNING: factor doesn't divide n

is written endless.

the log-file contains (many times):
[code]
Cofactor 336756866798891081 (18 digits)

c18: running rho...

c18: running qs (yafu)...
05/30/09 16:12:24 v1.10 @ HOME, Starting SQUFOF on 336756866798891081
05/30/09 16:12:24 v1.10 @ HOME, prp1 = 3
05/30/09 16:12:24 v1.10 @ HOME, C18 = 112252288932963693

Cofactor 336756866798891081 (18 digits)

c18: running rho...

c18: running qs (yafu)...
05/30/09 16:12:24 v1.10 @ HOME, Starting SQUFOF on 336756866798891081
05/30/09 16:12:24 v1.10 @ HOME, prp1 = 3
05/30/09 16:12:24 v1.10 @ HOME, C18 = 112252288932963693

(...)
[/code]

the session-log contains:

[code]
05/30/09 16:12:24 v1.10 @ HOME, Initializing with Tom's Fast Math (x86-32 asm)...
05/30/09 16:12:24 v1.10 @ HOME, cached 78504 primes. pmax = 1000099
05/30/09 16:12:24 v1.10 @ HOME, detected cpu 6, with L1 = 32768 bytes, L2 = 4194304 bytes
05/30/09 16:12:24 v1.10 @ HOME, New random seeds: 2192197217, 1243373184

05/30/09 16:12:24 v1.10 @ HOME, Processing expression: siqs(336756866798891081)

05/30/09 16:12:24 v1.10 @ HOME, Initializing with Tom's Fast Math (x86-32 asm)...
05/30/09 16:12:24 v1.10 @ HOME, cached 78504 primes. pmax = 1000099
05/30/09 16:12:24 v1.10 @ HOME, detected cpu 6, with L1 = 32768 bytes, L2 = 4194304 bytes
05/30/09 16:12:24 v1.10 @ HOME, New random seeds: 3888993488, 289474976

(...)
[/code]

any suggestions?

(no need to hassle, factorized it with other program)

[QUOTE=kar_bon;175323]
in DOS-window the message

WARNING: factor doesn't divide n

is written endless.[/QUOTE]

Well, the endless repetition isn't Ben's fault. It's mine! :blush: Though it's kinda by design. If yafu fails for some reason, aliqueit will try to run msieve instead. If msieve also fails (or isn't installed) yafu gets another shot at it. In this case it seems yafu always fails to factor the number so aliqueit loops endlessly.

EDIT: eh... maybe I should read your msg more closely. It's all Ben's fault! :razz: That 3 factor certainly doesn't divide the input number.

Yep, my bad. Thanks kar_bon for your report. Turns out it was always possible to return the last multiplier as a factor, which was always 1 until I changed the ordering of multipliers per the discussion in posts #143 - #153. Now the last multiplier is 3, so that if no valid factor is found, 3 is returned.

These invalid factorizations don't affect double large prime siqs because the (invalid) cofactor will be too large and will be rejected if the bug occurs. If it does happen to be small enough and is saved, the relation will get thrown away during filtering.

I'll try to get new binaries with this fix posted soon, at least. The official next revision is still a ways out, since I've had zero time to work on code development. Lousy real life :smile:.

[quote=mklasson;175330]EDIT: eh... maybe I should read your msg more closely. It's all Ben's fault! :razz: That 3 factor certainly doesn't divide the input number.[/quote]

Well, maybe not all mine, yafu's Rho catches the factor :whistle:

[CODE][SIZE=2]
05/30/09 21:30:33 v1.10 @ sidious, Starting rho method on 336756866798891081
05/30/09 21:30:33 v1.10 @ sidious, Input has 59 bits, 1000 max iterations per poly
05/30/09 21:30:33 v1.10 @ sidious, poly x^2 + 1: found prp8 = 14113663 in 0.0100 sec
[/SIZE][/CODE]

Here's just one more debug case (I think I've seen more than one, but this one I saved):
[FONT=Arial Narrow][B]# yafu "siqs(1288372004431120823)"[/B][/FONT]
while rho, indeed, works in this case, too:
[FONT=Arial Narrow][B]# yafu "rho(1288372004431120823)"[/B][/FONT]

could yafu's rho be added to aliqueit?

[QUOTE=henryzz;175372]could yafu's rho be added to aliqueit?[/QUOTE]

Aliqueit used to let yafu run rho, but then I wrote an internal one for a slight speedup (insignificant on realistically sized numbers of course, but it was fun too :smile:).

[QUOTE=bsquared;175359]Well, maybe not all mine, yafu's Rho catches the factor :whistle:[/quote]

Curiouser and curiouser! I run 15k iterations of x^2+1. I only check every 100 steps though and don't bother trying to crack full n finds. Maybe I should...

[quote=mklasson;175377]Aliqueit used to let yafu run rho, but then I wrote an internal one for a slight speedup (insignificant on realistically sized numbers of course, but it was fun too :smile:).



Curiouser and curiouser! I run 15k iterations of x^2+1. I only check every 100 steps though and don't bother trying to crack full n finds. Maybe I should...[/quote]
it looks like yafu's rho finds more factors:smile:

[QUOTE=henryzz;175386]it looks like yafu's rho finds more factors:smile:[/QUOTE]

Yeah, for the above mentioned reason mostly. It would be nice if I fixed the "problem", but it's not high on my todo list right now. :smile: Yafu also uses some other polynomials, but my benchmarking (on alq_840) was better off just doing more iterations of x^2+1 instead.

Sorry to hijack your thread, Ben. :surrender

[quote=mklasson;175388]Yeah, for the above mentioned reason mostly. It would be nice if I fixed the "problem", but it's not high on my todo list right now. :smile: Yafu also uses some other polynomials, but my benchmarking (on alq_840) was better off just doing more iterations of x^2+1 instead.

Sorry to hijack your thread, Ben. :surrender[/quote]
would it be possible in your next version to have the option to change to yafu's rho?

[QUOTE=henryzz;175389]would it be possible in your next version to have the option to change to yafu's rho?[/QUOTE]

My initial reaction is "no" as it seems pointless. Even if my rho as is misses an occasional factor it's still much faster than calling on yafu's rho to do the job because of overhead from parsing and whatnot.

If you can compile aliqueit you can try it out for yourself by uncommenting the three lines under
[code]//use yafu's rho[/code]

Let's take any further discussion of this to the aliqueit thread.