Modulo Arithmetic

[Astro]

Hi,

I guess I need the FPU for this?

Is there a listing of FPU op codes, like opcodes.chm in the MASM help folder?

Best regards,
Robin.

[dedndave]

use the forum search tool
if you use advanced search - look for modulo division (i think) - responses from E^cube only
he was asking about this some time ago

[clive]

There isn't a modulo function in floating point. ie you get a fractional result, not a remainder.

A quick grab of the 'F' opcodes gives

Code Select Expand

f2xm1
fabs
fadd
faddp
fbld
fbstp
fchs
fcmovb
fcmovbe
fcmove
fcmovnb
fcmovnbe
fcmovne
fcmovnu
fcmovu
fcom
fcom2
fcomi
fcomip
fcomp
fcomp3
fcomp5
fcompp
fcos
fdecstp
fdisi
fdiv
fdivp
fdivr
fdivrp
femms
feni
ffree
ffreep
fiadd
ficom
ficomp
fidiv
fidivr
fild
fimul
fincstp
fist
fistp
fisttp
fisub
fisubr
fld
fld1
fldcw
fldenv
fldl2e
fldl2t
fldlg2
fldln2
fldpi
fldz
fmul
fmulp
fnclex
fninit
fnop
fnsave
fnstcw
fnstenv
fnstsw
fpatan
fprem
fprem1
fptan
frndint
frstor
fscale
fsetpm
fsin
fsincos
fsqrt
fst
fstp
fstp1
fstp8
fstp9
fsub
fsubp
fsubr
fsubrp
ftst
fucom
fucomi
fucomip
fucomp
fucompp
fxam
fxch
fxch4
fxch7
fxrstor
fxsave
fxtract
fyl2x
fyl2xp1


-Clive

[oex]

xor edx, edx
mov eax, 10
mov ecx, 3
div ecx

eax contains 3
edx contains 1

[clive]

I guess we'd need to guess at the point/usage being looked for. Usually, I'd be interested in separating the integer and fractional parts, and not screwing up the rounding.
For example with 59.9999999 seconds, and "large" values of 0.9999999 becoming 1.0 when it is technically still smaller. (There are precision issues representing base 10 numbers in base 2, removing the most significant digits suddenly causes additional precision to appear in the least significant ones)

-Clive

[qWord]

Is there a listing of FPU op codes

AMD64 Architecture Programmer's Manual Volume 5: 64-Bit Media and x87 Floating-Point Instructions

[Astro]

Hi,

Great!

I want to do arbitrary precision math.

use the forum search tool

Good point! I visit more forums where it is broken or disabled than where they work so I don't tend to think about it.

if you use advanced search - look for modulo division (i think) - responses from E^cube only
he was asking about this some time ago

OK!

Best regards,
Robin.

[dedndave]

Drizz has a bignum library on his webpage - not sure about modulo division
but, if you wanted to, you could divide, then modulus = dividend - (quotient x divisor)

[raymond]

I want to do arbitrary precision math.

The FPU will give you at most 64 bits of precision (equivalent to approx. 19 decimal digits). That precision can be less depending on the precision of the input and the type/quantity of operations performed to the input.

Arbitrary precision is generaly regarded as requiring significantly more than the 64 bits of precision, such that the use of the FPU cannot be sufficiently precise. You then have to rely on integer operations to provide the required precision.

If you only need the basic arithmetic operations such as addition, subtraction and multiplications, this can be achieve easily. Divisions by large numbers will be a little more difficult. Computing logarithms, exponentials and trigonometric functions is considerably more difficult.

I don't know what your objectives are but I wish you the best in your endeavour.

[Astro]

I want to implement the Blum Blum Shub algorithm - it is a CSPRNG based on the same principles as RSA.

http://en.wikipedia.org/wiki/Blum_blum_shub

Best regards,
Robin.

[Eddy]

Blum-Blum-Shub PRNG requires the use of big numbers, so the FPU will be not much good to you.
You need to use a bignum library as Dave already suggested.

Kind regards

[dedndave]

i remember seeing Blum Blum Shub in here before - you might try the forum search tool

[raymond]

I want to implement the Blum Blum Shub algorithm

That algo is designed to generate pseudo random numbers. You have not mentioned the range you intend to generate.

If that range is within the range of a dword (less than 32 bits), you don't need a bignum library, and you need not use the FPU. If your intention is for encryption with ultra-high security, that is a totally different ball game; then you need to use a bignum library of functions which you either write yourself or adapt from someone else's work.

[dsouza123]

A version of Blum Blum Shub with dword sized p and q.

[Astro]

Hi,

Thanks dsouza123!

The range I'm looking at is large - upwards of 2048-bit. After posting here I actually starting taking issue with the fact it was pseudo, and contemplated finding a hardware source. I was also reading that B-B-S may have a serious weakness in its algorithm due to the way the numbers are generated, and that it seems it might be possible to influence the output or determine its state.

The more I read the less I liked about any of it, and wondered if it was worth the hassle.

I did wonder about an alternating step generator with a very long period. It seems to be as solid as anything, and the start state can be generated easily, and it seems, securely, if a hash of the output is fed back in as an input. It could then be initialized by running it for a random length of time before taking bits from it so its state is unknown. It also simplifies it as I don't have to mess around finding primes.

* Generate random data
* hash it
* hash the output several times, adding random data to the mix
* insert this output as the start state of the LFSR
* run the LFSR for a time
* start taking bits from it

Best regards,
Robin.