Wednesday, August 24, 2005

Is This Number Prime...??? : One

Is this a New Idea...???
---
The other day i was thinking of how Prime Numbers always have to end in either a One, Three, Seven or Nine... and that if they end with anything else, they have to be 'Composite'...???
Well-- My brain continued... wouldn't it be nice if you could simply convert a number to a different base,
then look at the last digit ( right most ) and see if that indicates Compositibility...
Say like; 2081 might be prime, but it might be composite as well...
In Hexidecimal; 2081 = 81
All Hexidecimal Primes have to end with 1, 3, 5, 7, 9, B, D, or F
Which is Not much help...
In base 6; Primes have to end with a 1 or 5
2081 in base 6 is 13345
So it could still be Prime...!
---
List of Composite Indicators for Various Bases...
Base: Ending Character that means Definitive Compositeness
The Inverse Characters; ( 1 3 7 9 ) for Base 10, for example;
May mean that the Number is Prime, But it may be Composite as well...???
This Technique is designed to Spot Definitive Compositeness only!
But-- ( more later... )
02 : 0
03 : 0
04 : 0 2
05 : 0
06 : 0 2 3 4
07 : 0
08 : 0 2 4 6
09 : 0 3 6
10 : 0 2 4 5 6 8
11 : 0
12 : 0 2 3 4 6 8 9 A
13 : 0
14 : 0 2 4 6 7 8 A C
15 : 0 3 5 6 9 A C
16 : 0 2 4 6 8 A C E
17 : 0
18 : 0 2 3 4 6 8 9 A C E F G
19 : 0
20 : 0 2 4 5 6 8 A C E F G I
21 : 0 3 6 7 9 C E F I
22 : 0 2 4 6 8 A B C E G I K
23 : 0
24 : 0 2 3 4 6 8 9 A C E F G I K L M
25 : 0 5 A F K
26 : 0 2 4 6 8 A C D E G I K M O
27 : 0 3 6 9 C F I L O
28 : 0 2 4 6 7 8 A C E G I K L M O Q
29 : 0
30 : 0 2 3 4 5 6 8 9 A C E F G I K L M O P Q R S
31 : 0
32 : 0 2 4 6 8 A C E G I K M O Q S U
33 : 0 3 6 9 B C F I L M O R U
34 : 0 2 4 6 8 A C E G H I K M O Q S U W
35 : 0 5 7 A E F K L S U
36 : 0 2 3 4 6 8 9 A C E F G I K L M O Q R S U W X Y
After 36; you have to get creative with your characters...!!!
---
Is there a magic test that could use this approach to determine if a number were really Prime or really Composite...???
It turns out that there is...
But over the last few days, i've been oscillating between, Yes & No...!!! ( ? )
One thing that i discovered was that Only Prime Bases were Useful in determining the Primeness of a given number... And they are the least interesting in Base Conversions...
i was thinking that if an Alien Race of Beings were to have selected a Prime Number as their Base for Mathematics... They may very well have missed the whole idea of Prime Numbers...!
It turns out that superficially, Primes in Prime Bases don't looks any different from Composite Numbers...!!! Prime numbers in Base 7 or 11 or 13 ( ...et. al. ) can end with any digit a Composite number can...
Except Zero...!
Which is exactly what makes them useful for our purposes...!
---
So the way to do this ( it sounds crazy, so bear with me...! )
Is to simply take a number that you'd like to know is prime or not,
Then convert it to The Base that is; The Product of All The Prime Numbers
SmallerThan or EqualTo The Square Root of your Mysterious Number!
Since i've been playing around with this on my HP48,
And since it can only handle numbers with 12 digit precision,
And even so, If you divide a 12 digit number by 2 ( say )
The results may not be entirely correct...!
So in actual practice, you can't work with numbers over 11 digits...
( unless you do something crazy to them first...!!! )

---
OK...
So like lets pick 2793 and ask if it's Prime...?
It's square root is 52.8, so you'd make list of all the prime numbers up to 52;
{ 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 }
Then multiple them all together...
Which is 6.14E17
Which is too big for us...
---
OK...
Lets try... 287
It's square root is 16.94, So it's list would be:
{ 2 3 5 7 11 13 }
Which comes to 30030!
That's the BASE were going to use...
Ordinarily; When you convert a number to a new base,
Each digit has it's own symbol...
With a base no higher than 36,
You can use the usual numbers & Then the alphabet,
But with a base of 30030,
Finding enough symbols that make any kind of sense--
Becomes a problem...!
So i've simply listed the value of each 'Place' with Decimal Numbers...
So that while 287 in Hexidecimal would be: 11F
In my Infinite Potential Base Notation;
287 in Hexidecimal would be [1] [1] [15]
OK -- Are we Clear on that...
---
So 287 in Base 30030 would be:
[287]
That's it.
This entire scheme is meant to be used with very large numbers
So that it kind of looses it's Flash when working with such small numbers...
But the gist of it is that you'd then take the last 'digit',
Which in this case is 287 and ask:
Can it be factored by any of the Primes in your Primes List...
{ 2 3 5 7 11 13 }
---
In the listing above of the first 36 Bases, It includes all the Composite Indicators...
But with a Base of 30030, that would be a pretty long list...
Even so, if you can create a look-up-table of those digits,
( Which would be especially useful if your Primes List was Hundreds or Thousands of Numbers Long...!!! )
It might be faster than checking the last 'digit' by conventional methods...
But still-- The last 'digit' might be comparitively small, so that it would be easy to check...
The strength of this method, i think, is that you can check a whole bunch of numbers in essentially 'One Step'...
And after the Base Conversion;
The last 'digit' might reveal the Compositeness of the Mystery Number Outright...!
---
And yes 287 can... So that means that it's Definitely Composite.
If you used all the Primes that you needed to, and it Passed...
( That is; Flunked all The Definitely Composite Tests... )
Then it would Definitely be Prime!
---
Is this Useful...?
It seems to me that if you were checking a large number,
And you had a computer that could work with large numbers,
And even if you didn't have a list of all the Primes up to
The Square Root of your Mystery Number,
You could still use all the Primes that you Did Have,
And Check for Compositeness up to that point.
---
This test primarily tests for Definite Compositeness in it's Incomplete Form,
and failing that, The number may or may not be Prime.
---
So lets redo the test,
But this time, only use the Prime Numbers
{ 2 3 5 }
2 times 3 times 5 = 30
287 in base 30 is: ( Base 30: 9H )
Infintie Potential Base Notation: 30: [9] [17]
The Last Digit is [ 17 ]
and 17 is prime for 2, 3, or 5.
So it's Not Definitely Composite.
And it Might Be Prime...
It just turns out that it isn't.
287 factors out to: 7 times 41
---
On a related Topic...
It seems to me that these Codes that require the really big Primes are vulnerable to this sort of attack...???
i am wondering... Where do you get the 'little' Prime Numbers to make the BIG Composite Number that becomes The Public Key...???
Is there an Index of them somewhere...
Why don't the Hacks that are trying to break the Big Composite Number, simply look through this Index, and try them first...???
Or-- If they come from 'Somewhere Else'...???
Then why can't you simply determine the Square Root of
The Big Composite Public Key & Assume that
the little Primes are somewhere around there...
( after all, they should be as big as possible,
and the square root would delimit their largeness... )
i realize that with a 500 digit Public Key,
The Range of Numbers that i'm asking you to search would be pretty big,
but it seems like it would be alot smarter to start at the top and work down--
Rather than work up from teeny tiny primes that no one in their right mind would use...???
---
....................
Here's the listing for my Prime Base Searcher:
As always: This stupid Blog HTML interpreter is Massively Weird,
and will not allow me use symbols which would make this easy to read...!!!
Sssooorrrrrryyy...!!!

Input is:
2: List of Primes
1: Mystery Integer Number

'C.P?'
--
OVER 1 + (PI)LIST (rightarrow) p x B
--
x B (rightarrow) c
--
STD IP { } SWAP
WHILE DUP c (greaterthanorequalto)
REPEAT c /
DUP FP c * (zero) RND
ROT + SWAP IP
END
SWAP +
DUP OBJ- 1 2 -LIST -ARRY
"Base." B + -TAG SWAP DUP SIZE
GET (rightarrow) -d
--
p p p -d (squareroot)
(zero) RND x.L? NOT :: HEAD IFT
POS 1 SWAP SUB 1
--
-d OVER / FP CEIL :: DROP IFT
--
DOLIST
DUP TYPE 5 (equalequal)
--
"Composite" -TAG
--
--
"UnKnown"
--
IFTE
--
--
--
--

This looks through a list to find the best match...
Input is:
2: { List of numbers }
1: Number

'x.L?'
--
OVER SIZE DUP 2 / (zero) (rightarrow) L x u m d
--
L SORT
WHILE m u (notequal) m d (notequal) AND
REPEAT
DUP m GET x (lessthan)
--
m 'd' STO u m - 2 / (zero) RND 'm' STO+
--
--
m 'u' STO m d - 2 / (zero) RND d + 'm' STO
--
IFTE
END
x OVER m GET - SIGN (rightarrow) p
--
CASE
p -1 (equalequal) THEN m 1 - m SUB END
p (zero) (equalequal) THEN m GET END
p 1 (equalequal) THEN m m 1 + SUB END
END
DUP TYPE NOT
--
--
--
---
Output is either a perfect match:
2: Original Number on 1:
1: 1
or
2: { lower & upper limits }
1: 0

---
Bonus Program:
My Prime Finder
Input is:
1: Integer

'Prm?'
--
CLLCD DUP { }
SWAP 2 SWAP (zero) 1 FOR z
z
DO
2 PICK 4 DISP
DO
2 + DUP 4 PICK SWAP - 2 DISP
DUP2 / FP NOT
UNTIL
4 PICK 3 PICK (lessthan) OR
END
DUP 4 ROLL (lessthanorequalto)
--
DUP 4 ROLL SWAP + 3 ROLLD
DUP 2 - 3 ROLLD /
z
--
DUP (squareroot)
--
2
IFTE
CEIL IP SWAP ROT (zero)
--
--
DROP DUP (squareroot)
CEIL IP SWAP 1
--
IFTE
UNTIL
END
NEXT
SWAP DROP DUP 1 (morethan)
--
+
--
--
DROP
--
IFTE
--

----------------Terminus :