View Single Post
Old 2014-04-11, 03:53   #22
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3×2,953 Posts
Default

Now you got to more realistic times :D
Related to your question, there are many ways to get that order, without factoring. Unfortunately none of them is faster.

One very simple (but still exponential) method is extremely easy to implement in binary, as it only needs additions and shifts:

Starting with 1:
-- add q
-- count the (binary) zeroes at the end, and eliminate them
-- repeat the two steps above until you get 1.

Example:
say q=5, which in binary is 101, so 101+1=110, we have 11 and a zero.
-- 11+101=1000, we have 1 (so we stop) and additional 3 zeroes, so we have a total of 4 zeroes. Therefore 5 divides 24-1, more exactly 5 divides all numbers of the form 24k-1, and none others (i.e. there is no other power x such as 2x-1 is divisible by 5)

You can do this for all odd numbers (not necessarily prime) and there is a simple proof that you will always end in 1, after the right number of steps.

say q=9, which in binary is 1001, so 1001+1=1010, we have 101 and a zero.
-- 101+1001=1110, we have 111 and additional one zero, total 2 zeroes.
-- 111+1001=10000, we have 1 (so we stop) and additional 4 zeroes, total 6 zeroes.
Therefore, 9 divides 2^6-1, and all numbers of the form 26k-1 and none others.

say q=11 (decimal), which in binary is 1011, so 1011+1=1100, we have 11 and 2 zeroes.
-- 11+1011=1110, we have 111 and additional one zero, total 3 zeroes.
-- 111+1011=10010, we have 1001 and additional 1 zero, total 4 zeroes.
-- 1001+1011=10100, we have 101 and additional 2 zeroes, total 6 zeroes.
-- 101+1011=10000, we have 1 (so we stop) and additional 4 zeroes, total 10 zeroes.
Therefore, 11 divides 2^10-1, and all numbers of the form 210k-1 and none others.

One which will interest us, where the result is prime:

say q=23, which in binary is 10111, so 10111+1=11000, we have 11 and 3 zeroes.
-- 11+10111=11010, we have 1101 and additional one zero, total 4 zeroes.
-- 1101+10111=100100, we have 1001 and additional 2 zeroes, total 6 zeroes.
-- 1001+10111=10000, we have 1 (so we stop) and additional 5 zeroes, total 11 (decimal) zeroes.
Therefore, 23 divides 2^11-1, and all numbers of the form 211k-1 and none others.

The same (last) calculus in decimal, involving "divide by 2 if it is even", would look like:
q=23+1=24, even, we have q=q/2=12 and p=1 (one zero);
q=12 even, we have q=6 and p=2;
q=6 even we have q=3 and p=3;
q=3 odd, etc...
q=3+23=26, q=13, p=4;
q=13+23=36; q=18, p=5; q=9, p=6;
q=9+23=32; q=16, p=7; q=8, p=8; q=4, p=9; q=2, p=10; q=1, p=11; end.
So, 23 divides 2^11-1.

Next step, you have to do an ASIC to compute this (it won't be difficult, anyhow it is much simpler than the asics for sha256 for bitcoin mining, hehe, just few counters and shifters) but it will still be (much) slower than normal exponentiation, by squaring - but well... you do no factoring, neither multiplication nor division ).

Last fiddled with by LaurV on 2014-04-11 at 04:01
LaurV is online now   Reply With Quote