Qbasicnews.com
April 12, 2021, 07:21:09 PM
 Pages: 1 [2]
 Author Topic: A different and better way to find prime numbers  (Read 19777 times)
Moneo
Na_th_an

Posts: 1971

 « Reply #15 on: September 19, 2005, 08:35:03 PM »

Hey guys,

The subject of this thread is determining prime numbers. This may sound strange to some of you, but in 44 years of programming I have never had to work with prime numbers.

Could some of you give me a practical application or some examples where you need to work with prime numbers. Just curious.
*****
 Logged
Sterling Christensen
Na_th_an

Posts: 1328

 « Reply #16 on: September 19, 2005, 09:00:30 PM »

Quote from: "Moneo"
Could some of you give me a practical application or some examples where you need to work with prime numbers. Just curious.

Encryption

Ladies and gentlemen, introducing the latest internet innovation: E-cryption  :oops:
 Logged
rpgfan3233
Ancient Guru

Posts: 617

 « Reply #17 on: September 19, 2005, 09:34:10 PM »

Quote from: "Sterling Christensen"
Ecryption

Encryption? A good idea, but how would you differentiate between prime numbers, such as 23 VS 233? Would numbers with less than 4 digits be converted to 4-digit numbers using zeroes for padding or something (I do that for octal and hexadecimal usually)?
 Logged

974277320612072617420666C61696C21 (Hexadecimal for those who don't know)
Sterling Christensen
Na_th_an

Posts: 1328

 « Reply #18 on: September 20, 2005, 12:08:27 AM »

Quote from: "rpgfan3233"
Quote from: "Sterling Christensen"
Ecryption

Encryption? A good idea, but how would you differentiate between prime numbers, such as 23 VS 233? Would numbers with less than 4 digits be converted to 4-digit numbers using zeroes for padding or something (I do that for octal and hexadecimal usually)?

I dunno how it works... I just know most modern encryption techniques use prime numbers.
 Logged
rpgfan3233
Ancient Guru

Posts: 617

 « Reply #19 on: September 20, 2005, 12:12:00 AM »

Quote from: "Sterling Christensen"
I dunno how it works... I just know must modern encryption techniques use prime numbers.

Really? I always thought encryption was mainly 64-bit and 128-bit nowadays. I guess that shows my (lack of) knowledge of encryption techniques. :-P
 Logged

974277320612072617420666C61696C21 (Hexadecimal for those who don't know)
Z!re
*/-\*

Posts: 4599

 « Reply #20 on: September 20, 2005, 07:21:58 AM »

The bit number in an encryption refers to the key lenght..

It has actually little to do with how safe the encryption actually is..
A 64bit encryption could very well be safer than a 2048bit one.. as it plays down to the actuall algorithm too.. which, sadly, many modern crypto programs keep hidden..

A good encryption is safe even if the "hacker" has access to the full sourcecode..

And ya, modern encryptions use two extremely high prime numbers multiplied together to create the final key..

There's some research that is pointing towards this being a bad way though, as there might be an algorithm for finding prime numbers more efficient than the current ones of testing each number up to the one you want..

I can't remember the website that has the research data though, do a google if you're interessted.. It was reported on the news here in sweden a few years ago..
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #21 on: September 20, 2005, 10:14:36 PM »

Quote from: "Sterling Christensen"
Quote from: "Moneo"
Could some of you give me a practical application or some examples where you need to work with prime numbers. Just curious.

Encryption

Ladies and gentlemen, introducing the latest internet innovation: E-cryption  :oops:

Well, like the saying goes "you learn something every day."
I didn't know that prime numbers were used in encryption algorithms.

I designed my own encryption algorithm back in 1975 for ATM transactions at Citibank NY, and I didn't use prime numbers. It would not have occurred to me to do so.
*****
 Logged
jakeman922
Member

Posts: 74

 « Reply #22 on: September 22, 2005, 10:20:19 PM »

Quote from: "Moneo"
Jake and Rpgfan,

Either of your solutions seem to work ok.

However, for some strange reason, if the input number "n" is greater than 2,147,483,647, which is the maximum value for a LONG integer, you will get an Error 06: overflow error, when the MOD instruction gets executed.

I consulted the QB Online Help plus my Quickbasic manual and there is no mention of any maximum values for the MOD operator. However, it does mention that "real" values will be rounded to integers, and this could be a clue as to why the maximum is a long integer.

So, the bottom line is that if your number is equal or greater than 2,147,483,647 then you can't use a MOD in your logic to determine if it's a prime number.
*****

Actually, there is an algorithim for figuring out modulo arithmetic for very large numbers, but I forgot it a long time ago.
 Logged

quote="Bruce Raeman"]Anatomy (n): something everyone has, but which looks better on a girl[/quote]
Dio
I hold this place together

Posts: 874

 « Reply #23 on: September 22, 2005, 11:24:03 PM »

hey i made a program that spews prime numbers!

Code:
a = -1
do
a = a +2
for i = 2 to a - 1
if a mod i = 0 then c = 1
next
if c = 0 then ? a
c = 0
loop

and one that produces a random prime number in a specified range:

Code:
max = 10000
min = 5000
1
x = int((max-min+1)*rnd+min)
for i = 2 to x - 1
if x mod i = 0 then goto 1
next
? x
sleep

and a website that features a bear that sh*ts prime numbers!

http://members.surfeu.fi/kklaine/primebear.html

i'm so proud of myself... :bounce:
 Logged

quote="whitetiger0990"]whitetiger is.. WHITE POWER!!! [/quote]
Here
Agamemnus
x/ \z

Posts: 3491

 « Reply #24 on: September 29, 2005, 06:24:59 PM »

ROFL.
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Mango
Wandering Guru

Posts: 360

 « Reply #25 on: October 04, 2005, 01:36:30 AM »

nice post dio, and on the floor with aga...

a challenge...the slowest prime generator where *every* bit of code is crucial.  I know of a prime generator that is made within Conway's Life...it's about 4 orders of magnitude slower than dio's...and it's an absolute work of art.
 Logged
 Pages: 1 [2]