B1g Numbers - C++

[SargeRX8]

If i want to calculate 5^58 in C++ where can i store it? I need to use the figure received later on for other calculations n ****.

Any help?

[Strik3r]

you will need to write/use a custom class.

the largest number you can easily use in c++ is(i believe) an unsigned long long

but that wont store the number you are talking about.. You have a few options.. google 'big int class c++' to find a few premade ones or write your own.

Or alternatively write a class that can store the number in scientific notation and perform operations on it (such as adding, subtracting, multiplying, dividing, etc.)

[Strik3r]

p.s. 5^58 is absolutely massive..... i suggest that for numbers of that scale you may want to consider option b and store it/manipulate it in scientific notation.

[Khaless]

I would suggest against writing your own class... To many mistakes to be had...
I believe there are abstractions floating around to deal with big numbers of almost unlimited range.. Find one of these, Google is your friend.

[ivo]

storing it is fine... manipulating it is the problem. Do as the Khaless said; surely there must be others around who have also played with big numbers....

[SargeRX8]

Example: I want to calculate 5^58 mod 97.

[Khaless]

Originally Posted by SargeRX8

Example: I want to calculate 5^58 mod 97.

Oh thats a different story.

I think we can worth this out better mathematically. Specifically using modulo arithmetic (google it!)

Think about this

5^58 = (5^29)^2

= (5^25 * 5^4)^2
=((5^5)^5 * 5^4)^2


Now 5^5 = 3125 (easy to work out with our current range)
5^4 = 625

so

5^5 % 97 = 21
and
5^4 % 97 = 43

so we have:
(21^5 * 43)^2

21^5 % 97 = 13

so
(13 * 43) ^ 2 % 97 = 44

So 5^58 % 97 = 44 and we did not need to use any large ints


Or you use python
>>> 5**58 % 97
44L

[ivo]

If you look up public cryptography and/or RSA code, there should be code for dealing with modulo arithmetic.

Also theres some sort of shortcut I think...
http://en.wikipedia.org/wiki/RSA#Encryption:
says it a few lines down

I forget the exact method now

[Khaless]

You know I figured it would be easier if I turn it into an algorithm for you... Can you tell I like Ruby more then Python

PYTHON:

def pow_mod(base, pow, mod):
mult = 1
for i in xrange(0, pow):
mult = (mult * base) % mod
return mult

>>> pow_mod(5, 58, 97)
44

RUBY:

def pow_mod(base, pow, mod)
(1..pow).inject(1) { |mult, x| (mult * base) % mod }
end

irb(main):060:0> pow_mod(5, 58, 97)
=> 44

[Khaless]

Better Yet:

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

[SargeRX8]

Ive gotta implement the Diffie Hellman key exchange system and use a square and multiple algorithm

Ill check out them links. Cheers

[Khaless]

DH should be fairly easy to implement given that you now know how to easily do modular exponentiation.

Here is a quick example I whipped up in IRB

irb(main):008:0> g, p, a, b = 5, 26, 14, 19
=> [5, 26, 14, 19]
irb(main):009:0> ga = g**a%p
=> 25
irb(main):010:0> gb=g**b%p
=> 21
irb(main):011:0> a_shared = gb**a%p
=> 25
irb(main):012:0> b_shared = ga**b%p
=> 25

[siBE]

tbh id just use lolcode or brain****

[SargeRX8]

this is brain****, my brain is ****ed.

[SargeRX8]

Ok ive got a "square and multiply" function which calculates the the above function(a^b mod n).

I now have a second piece of **** on the path.

Anyone know what i need to be able to calculate primitive root of x? I need to choose any particular primitive root of x to perform calculations on.

[God]

Lol we have an assignment exactly like that with C that i have yet to start, it includes polish notation ;(

[SargeRX8]

Originally Posted by God

Lol we have an assignment exactly like that with C that i have yet to start, it includes polish notation ;(

I finished it. I dont know what polish notation is, do you want my code? Its C++, easily adapted to C.

[Khaless]

Originally Posted by SargeRX8

I finished it. I dont know what polish notation is, do you want my code? Its C++, easily adapted to C.

Polish notation is prefix notation...

I assume you still have nfi so here is an example:

infix notation = 3 + 5
prefix (polish) notation = + 3 5
postfix (reverse polish) notation = 3 5 +

Now, infix notation works for us (humans) however postfix notation (reverse polish notation) is great for machines which use a stack

so if we have something like this in infix: 3 + 5 + 6
in reverse polish its 3 5 + 6 +

Not so sure what polish (or prefix) is really good for.

One thing to note is that if we do this in infix notation
(3 + 5) * 3
3 + 5 * 3
are two different things, and thus the parenthesis are important.

however in reverse polish the first is
3 5 + 3 *
and the second is
3 5 3 * + (i think )

and we need no paren's

Disclaimer: It has been years since I have messed around with this stuff... I hope I did not mix it up

[SargeRX8]

Ah pre fix and post fix notation. Done that stuff back in Data structures and algorithms, just didnt remember the term polish notation.

[Khaless]

Originally Posted by SargeRX8

Ah pre fix and post fix notation. Done that stuff back in Data structures and algorithms, just didnt remember the term polish notation.

yeah its just another name for it , thats all, same thing.

[God]

Just remembered its reverse polish, woops! Still, its gonna be one gay assignment imo, except yours is a bit different.

Ours is "1 2 3 4 1 2 + - + * /" = "1/2*3+4-1+2" - i think thats how they want it done, should prob read the assignment sheet again