Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#26 2013-09-23 13:47:40

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 15,916
Website

Re: Large Prime

anonimnystefy wrote:

Is there something more simple we could try first?

Should we compare the secrets?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#27 2013-09-23 13:49:19

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,392

Re: Large Prime

Hm, we could. But, I will be able to do that after I get my good night's sleep. smile


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#28 2013-09-23 13:55:49

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 15,916
Website

Re: Large Prime

Isn't it already 3 o clock there? Do you remain awake for so long?

Anyway, goodnight smile


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#29 2013-09-23 15:00:28

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 15,916
Website

Re: Large Prime

http://pastebin.com/MyZtxUyu

import base64
def rc4crypt(data, key):
    x = 0
    box = range(256)
    for i in range(256):
        x = (x + box[i] + ord(key[i % len(key)])) % 256
        box[i], box[x] = box[x], box[i]
    x,y = 0, 0
    out = []
    for char in data:
        x = (x + 1) % 256
        y = (y + box[x]) % 256
        box[x], box[y] = box[y], box[x]
        out.append(chr(ord(char) ^ box[(box[x] + box[y]) % 256]))
    return ''.join(out)
    
def decode(message,key):
    return rc4crypt(base64.b64decode(message),key)
def encode(message,key):
	return base64.b64encode(rc4crypt(message,key))

key = raw_input('Enter secret here:\n')
message = raw_input('Enter message here:\n')

print 'If you wanted to encrypt, here\'s the cyphertext:', encode(message,key)
try:
	print 'If you wanted to decrypt, here\'s the plaintext:', decode(message,key)
except:
	pass

Instructions
1. Paste the above python code in a file and run in a python interpreter if you have one, else paste it to
a. ideone
b. repl.it
2. The program takes 2 lines of input from stdin. The first line accepts the secret and the second line accepts the cyphertext or plaintext
3. Enter your secret in the exact decimal form(because I could not find a better way, this should work until we get something better). For example, if your secret is 7000123, you just type in 7000123(or copypasta it).
4. Running it on a interpreter or on repl.it will prompt you to enter the secret and the message when you are expected to do so.
5. To run it on ideone, you are supposed to enter the secret and the message seperated by a newline in the stdin field before running the program.


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#30 2013-09-23 21:44:24

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 84,574

Re: Large Prime

Could you post the link to the video?

http://www.youtube.com/watch?v=40i9ujVJ040


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#31 2013-09-23 22:37:15

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,392

Re: Large Prime

nhmIfQZuJaeccvW/WqEvpFAHfI5I1yqkSXLLbZ0uhH8g


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#32 2013-09-24 00:08:13

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 15,916
Website

Re: Large Prime

anonimnystefy wrote:

nhmIfQZuJaeccvW/WqEvpFAHfI5I1yqkSXLLbZ0uhH8g

jxXbHUFJOPSGePnyFptuvR8MeIhJkg==


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#33 2013-09-24 00:19:40

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,392

Re: Large Prime

jxXbHUFJOPSGePnyFptuvR8MeIhJkg==

nwSIWA5lP/XUVOy5CcI8rxESf4JI0CCoSjc=


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#34 2013-09-24 00:29:22

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 15,916
Website

Re: Large Prime

anonimnystefy wrote:

nwSIWA5lP/XUVOy5CcI8rxESf4JI0CCoSjc=

khnMHBhvOfSBbv2+E4YrpR4bM5obky6pBn/AOYw0nX56Yc5bvQ==


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#35 2013-09-24 03:23:18

auyeungyat
Member
Registered: 2013-09-23
Posts: 15

Re: Large Prime

yes,I want a Terminal code.Thank you!

Offline

#36 2013-09-24 03:41:31

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 15,916
Website

Re: Large Prime

Hi;

What do you want a terminal code for?
If you're on mac, you probably already have python.
I have never used a mac, I do not know about the mac terminal. Still, I believe that I could help if I knew what code you need


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#37 2014-03-14 17:56:17

danaj
Member
Registered: 2014-03-03
Posts: 14

Re: Large Prime

I'm not sure if I should post, (1) it is somewhat necro-posting, (2) there seems to be another conversation going on about DH, and (3) I type way too much.  But regarding generating large primes, this is a good paper about generating n-bit random primes:  "Close to Uniform Prime Number Generation With Fewer Random Bits" by Fouque and Tibouchi available at eprint.iacr.org/2011/481.  For crypto, you may want to also look at FIPS 186-4.

PRIMEINC:  generate a random number in the range, run next_prime on it.  Simple and fast, but bad distribution.

Trivial:  Aka Monte Carlo method as in post 3.  Perfectly uniform, but uses excessive randomness and is very slow for large sizes.  A comment about the post 3 code: for sizes over 2 bits, you'd want to take n-2 random bits and then set bits n-1 and 0 -- there is no need to waste time and entropy testing even numbers.  A well written test will return almost instantly, but you wasted time getting all those bits -- if you're on an isolated headless server using /dev/random you may wait hours to get the next set.

Modified: Methods like Fouque and Tibouchi A1 or A2; Joye-Paillier, etc.  I use a somewhat similar method for odd ranges (e.g. for ranges not a power of 2).  These sacrifice some uniformity for big increases in speed and less entropy consumption.  (the entropy consumption may or may not matter to you, but sometimes it is important).

Provable primes, typically Shawe-Taylor or Maurer's FastPrime.  Common for crypto use.  You can find Shawe-Taylor in FIPS 186-4; Maurer's algorithm in his publicly available paper, Menezes's book, or various open source implementations.  These work by generating a small random prime using the trivial method, then generating a larger one by iterating with additional random input until proven with either Pocklington or its improved version from BLS theorem 3.  Then recurse to make successively larger primes.  They only generate a subset of the primes in the range (10% for Maurer's FastPrime, substantially less for Shawe-Taylor) but that typically doesn't matter.

openssl or other software.  Good and bad.  OpenSSL likely doesn't make some mistakes you may make.  But you have to make sure your platform has a recent version, your program actually calls the right executable, you send it the right arguments, you interpret the output and exceptions properly, you're ok with its decisions on randomness sources, you're OK with it not meeting FIPS 186-4 standards for primality testing, and know it is slower for sizes > 1024 than what can be done with GMP meeting the standards.


There are lots of other considerations.  E.g. where are you getting your randomness?  Are you using a good enough primality test for your purpose?  Do you need provable primes?  Strong primes?  Writing your own code is fun, but may have bugs -- do lots of testing.

Whether these are "quick" or not depends on the size, which method you choose, your implementations, and what you think quick means.  For 1024-bit primes, my older machine using Perl code generates them in 0.06s each (F&T algorithm 1, ISAAC seeded from /dev/random, BPSW + 1 M-R probable primes).  Add 0.006s for 3 additional random M-R plus a Frobenius test.  Add not much more for enough extra M-R tests to make FIPS 186-4 happy.  For smaller sizes sometimes running a primality proof on the n-bit prime is faster than a constructive method, but your mileage may vary.  At 1024 bits, my Maurer routine takes 0.65s, while Shawe-Taylor using FIPS 186-4 + SHA256 takes 0.24s.  The generation code is in Perl so it could be faster, but the heavy work ends up being in C+GMP.

Offline

Board footer

Powered by FluxBB