mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-01-26, 21:37   #12
Peleg_r
 

2×2,251 Posts
Default Primality tests

I understand you need some code to implement in a computer program. please specify the OS platform and programming language you preffer to work with and i'll see what i can do.

From what i gather you need to test primes up to 20 digits, is this correct?

Please reply here or at the user forum at www.shteker.com
  Reply With Quote
Old 2004-01-26, 21:51   #13
andi314
 
andi314's Avatar
 
Nov 2002

2×37 Posts
Default

I'm using win98 and c++

mostly i wirte my programs with the help of the MIRACL libary or the giantint library
andi314 is offline   Reply With Quote
Old 2004-01-27, 05:07   #14
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

Some basic background information on trial factoring.

Only need to test to the square root of the number.

For numbers expressed in base ten the square root will be at most one more than half the number of digits as the number your trying to factor.

A 15 digit number would have 8 digits max for the square root.

All primes except 2 and 3 are 6x +/- 1 with x = 1 ... so the factor mod 6 must be either 1 or 5 to be a potential prime.

A 64 bit unsigned integer can hold a 20 digit number (18446744073709551615 max).
dsouza123 is offline   Reply With Quote
Old 2004-01-27, 14:35   #15
andi314
 
andi314's Avatar
 
Nov 2002

7410 Posts
Default

but trial factoring a 20 -digit number take a while!!!

I want to implement a primility test where i know theat the number is 100% prime!!!
andi314 is offline   Reply With Quote
Old 2004-01-27, 17:21   #16
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2D6916 Posts
Default

Quote:
Originally Posted by andi314
so which other methods could i use to determine that a number is 100% prime???
For numbers having no special form, there are a number of algorithms you could try, e.g. APRCL (named after its inventors), ECPP, or the recent deterministic AKS algorithm. Do a Google search on any of these and you'll find background info and in most case freeware implementations. The practical limit of these seems to be 5000-10000 digits at present - proving any number < 100 digits or so would be virtually instantaneous via these methods.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Anti-poverty drug testing vs "high" tax deduction testing kladner Soap Box 3 2016-10-14 18:43
PRP testing pepi37 Software 6 2013-04-12 09:42
Testing grobie Marin's Mersenne-aries 1 2006-05-15 12:26
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53
P-1 Testing ndpowell Math 4 2005-06-26 20:14

All times are UTC. The time now is 12:07.

Wed Apr 14 12:07:35 UTC 2021 up 6 days, 6:48, 0 users, load averages: 2.75, 2.40, 2.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.