Prime check need

bggashnik · 2007-04-06, 19:16

Is there any site or program i can test if one array is prime number?You have to know that the array is very long number and the algoithm should be fast...Thank you in advance

akruppa · 2007-04-06, 19:21

What do you mean by "array?" Do you have an array of many large numbers to test, or maybe an array of "unsigned int" that form one large number? How large exactly is the number? Do you want a test that tells primality with extremely low, but non-zero probability of error, or does it have to be a mathematical proof?

Alex

bggashnik · 2007-04-06, 20:32

I mean string and "char" type.The lenght of the string is about 10 miliion symbols.Is there any software,code or algorithm to check if it is prime?

Mini-Geek · 2007-04-06, 21:25

Quote:

Originally Posted by bggashnik

I mean string and "char" type.The lenght of the string is about 10 miliion symbols.Is there any software,code or algorithm to check if it is prime?

10 million symbols that are how many different things per symbol? This makes a huge difference. There could be two things per symbol, in which case your number is 2^10000000, or, for all we know, it could be 10 million different per symbol, making it 10000000^10000000. Please clarify by saying how many digits it is and what form of number it is (or the number itself if you don't mind saying it), so we can figure out what factoring/primality test would be the most efficient.

ewmayer · 2007-04-06, 23:32

If by "symbol" he means anything encoding a single bit or more, no, there is no known algorithm to test 10M-symbol numbers not having any special algebraic form for rigorous primality.

A probably-prime test might be within reach, if the symbols are decimal digits or smaller.

potonono · 2007-04-07, 02:16

Quote:

I mean string and "char" type.The length of the string is about 10 miliion symbols.Is there any software,code or algorithm to check if it is prime?

I must be dealing with end users way to much since it sounds obviously clear to me that what we have is appoximately a 10 million digit number saved entirely as a string. We can access the individual digits as characters of the string's "array". I don't know if any algorithm to take a number in that form, but I haven't really looked either..

bggashnik · 2007-04-07, 07:37

The string contains about 10 million digits.I thought it isn't so difficult to understand.I read in this forum that i can test if the number is prime with prime95 program but first i should register myself in GIMPS project.Is it right?:surprised

bggashnik · 2007-04-07, 07:46

Quote:

Originally Posted by potonono

I must be dealingth end users way to much since it sounds obviously clear to me that what we have is appoximately a 10 million digit number saved entirely as a string. We can access the individual digits as characters of the string's "array". I don't know if any algorithm to take a number in that form, but I haven't really looked either..

yeah that's right!

I searched Google for java based sites which test if a number is prime but the limit of digits is only 20.The main problem is that I can't find anywhere algorithm or program which could test my string.

ET_ · 2007-04-07, 10:37

Quote:

Originally Posted by bggashnik

The string contains about 10 million digits.I thought it isn't so difficult to understand.I read in this forum that i can test if the number is prime with prime95 program but first i should register myself in GIMPS project.Is it right?:surprised

GIMPS can only prove primality of numbers of the form 2^p-1 with p prime.

If your number is not built on this form, you have no chance to test it.

Also please note that if you use GIMPS to test your number, and the number is prime, you must share the EFF prize as explained here.

Luigi

paulunderwood · 2007-04-07, 11:06

Quote:

Pfgw can work with numbers from 2 up to almost 2^79700000 (about 24000000 digits). It can find probable primes with Fermat's method, with bases from 2 to 256

from section A.3 of the pfgwdoc.txt file that comes with PFGW. That's 24 million decimal digits.

akruppa · 2007-04-07, 15:26

The question of whether you need a *proof* of primality, or merely a primality test with very small chance of error, is unanswered.

If you need the former, getting a positive result is out of the question, unless your number is of a very specific form. If the latter will do, PFGW sounds like a good way to go.

Alex

2007-04-06, 19:16	#1
bggashnik Apr 2007 4₁₆ Posts	Prime check need Is there any site or program i can test if one array is prime number?You have to know that the array is very long number and the algoithm should be fast...Thank you in advance

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Does mprime check prime.txt/local.txt for changes?	odin	Software	4	2010-04-16 05:59
Check the prime	Vandor	Information & Answers	3	2008-11-27 15:25
prime check myself	Vandor	Software	1	2008-10-10 05:52
easiest way to check if you found prime	Mini-Geek	No Prime Left Behind	33	2008-03-07 23:43
How to check if a number is a Mersenne prime ?	Unregistered	Software	6	2004-06-19 08:18

2007-04-06, 19:21	#2
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	What do you mean by "array?" Do you have an array of many large numbers to test, or maybe an array of "unsigned int" that form one large number? How large exactly is the number? Do you want a test that tells primality with extremely low, but non-zero probability of error, or does it have to be a mathematical proof? Alex

2007-04-06, 20:32	#3
bggashnik Apr 2007 2² Posts	I mean string and "char" type.The lenght of the string is about 10 miliion symbols.Is there any software,code or algorithm to check if it is prime?

2007-04-06, 23:32	#5
ewmayer ∂²ω=0 Sep 2002 República de California 2D60₁₆ Posts	If by "symbol" he means anything encoding a single bit or more, no, there is no known algorithm to test 10M-symbol numbers not having any special algebraic form for rigorous primality. A probably-prime test might be within reach, if the symbols are decimal digits or smaller.

2007-04-07, 07:37	#7
bggashnik Apr 2007 2² Posts	The string contains about 10 million digits.I thought it isn't so difficult to understand.I read in this forum that i can test if the number is prime with prime95 program but first i should register myself in GIMPS project.Is it right?:surprised

2007-04-07, 15:26	#11
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	The question of whether you need a proof of primality, or merely a primality test with very small chance of error, is unanswered. If you need the former, getting a positive result is out of the question, unless your number is of a very specific form. If the latter will do, PFGW sounds like a good way to go. Alex