Yafu

[Batalov]

The new binary nailed all three. Thanks!

In the end, when all factors are reported, the binary lingers for a second and then says
>> couldn't reallocate string when parsing
Exit 255
It doesn't hurt (really), but what is it doing for that second?
The command-line is
# echo "siqs(732566077883908909845195639793682175206731)" | yafu -v

Doesn't seem to "freeze" without -v.

[xilman]

Originally Posted by bsquared

Who knew that the ultimate question to the ultimate answer was "what size composite integer places excessive stress on yafu's hack of a random number generator?"? Only for 64 bit systems is this a problem, where I put some garbage together to try to extend rand() to produce a 64 bit random number rather than the 16 bit default.

If you want a cheap and cheerful 64-bit PRNG I recommend the MMIX LCG:

x[i+1] = (6364136223846793005*x[i] + 1442695040888963407) mod 2^64

If you want a good generator you need to do a bit more research.


Paul

[bsquared]

Originally Posted by Batalov

The new binary nailed all three. Thanks!

In the end, when all factors are reported, the binary lingers for a second and then says
>> couldn't reallocate string when parsing
Exit 255
It doesn't hurt (really), but what is it doing for that second?

Putting in a few cycles on computing the Ultimate Question, of course .

Originally Posted by Batalov

The command-line is
# echo "siqs(732566077883908909845195639793682175206731)" | yafu -v

Doesn't seem to "freeze" without -v.

On a more serious note, would you be upset to learn that it was stuck in a loop allocating more memory for a string? malloc eventually returns NULL, at which point the program notices and exits.

Everything works fine without the -v because the program is able to determine that there is something in the pipe, processes it, and exits. It gets confused with the -v because there is both something in the pipe and an input argument which causes it to open in interpreter mode. There is apparently a neverending stream of stuff coming out of an open pipe... .

A workaround until I can fix this is to just use yafu "siqs(732566077883908909845195639793682175206731)" -v, or use echo but put the v in the .ini file.

apologies,
- b.

[bsquared]

Originally Posted by xilman

If you want a cheap and cheerful 64-bit PRNG I recommend the MMIX LCG:

x[i+1] = (6364136223846793005*x[i] + 1442695040888963407) mod 2^64

If you want a good generator you need to do a bit more research.


Paul

Such as this?

[xilman]

Originally Posted by bsquared

Such as this?

Sure, if it meets your requirements. I don't know what "good" means in your context.

Until you know your requirements (speed, cycle length, cryptographic strength, code complexity, sundry statistical properties, etc) it is difficult to give advice other than to conduct research.

The 3rd Edition of Numerical Recipes has some nice proposals for non-cryptographic PRNGs.

My guess is that the MMIX may be sufficient for what you want, which is why I proposed it. It is certainly very quick to write and to run as it consists of two simple arithmetic operations on a 64-bit variable. It's what I use all the time when I can't justify anything more complex.

Paul

[bsquared]

Originally Posted by xilman

Sure, if it meets your requirements. I don't know what "good" means in your context.

That's a good question; me neither, really. Random numbers are used in many places throughout the code, but mostly for non-critical things like generating random ECM curve sigmas and random factor base indices from which SIQS polynomials are built, that sort of thing. MMIX, I'm sure, would be fine for those.

The only "mission critical" application from a RNG standpoint that I can think of is the RSA number generation function. But I've never meant that to be targeted for cryptographic use - only for generating test cases for siqs and other factoring routines.

Originally Posted by xilman

It's what I use all the time when I can't justify anything more complex.

Paul

Sounds a lot like my situation.

Thanks!
- ben.

[jrk]

Originally Posted by bsquared

Such as this?

Or this?

[bsquared]

Originally Posted by jrk

Or this?

Thanks! I hadn't seen that before.

[kar_bon]

Suggestion:

The output from yafu V1.18 in a DOS-box gives the length of the candidate like
rho: ... on C99
pp1: ... on C99
ecm: ... on C99 ...

but the file 'factor.log' only prints this in bit-size!

So could you equalize both outputs? I like the Cxx more.

[bsquared]

Originally Posted by kar_bon

Suggestion:

The output from yafu V1.18 in a DOS-box gives the length of the candidate like
rho: ... on C99
pp1: ... on C99
ecm: ... on C99 ...

but the file 'factor.log' only prints this in bit-size!

So could you equalize both outputs? I like the Cxx more.

Sure, thanks for the suggestion.

[bsquared]

... in the usual place.

New in version 1.19

+ much improved sieve of Eratosthenes
+ faster prime counting (fastest available on modern 64 bit CPUs in some situations)
+ higher limit (up to 4e18)
+ less memory usage
+ some new flags for printing primes.
+ slightly faster SQUFOF implementation
+ bugfixes
+ misc requested changes
+ addition of fermat's factorization algorithm

For this version I again mostly concentrated on the sieve of Eratosthenes. Also the usual bug fixes and requested changes. Any feedback is welcome.