SRL Archive - Help and Support

Because, for example, giant prime numbers make awesome keys. I want something that can promptly find the largest prime number closest to an inputted number that may (and might usually be) up to 4096 bytes. If it would make it faster, the length of the key in bytes and/or bits is a possibility.



I plan to glue a few hexadecimal strings together and make one huge ass key… No puny 64 bit ones here :p



NOTE: I like random numbers… Lots of random numbers. READ THE CRYPTONOMICON

I wrote a prime finder about a year ago, I doubt I still have it, but basically it did this:

Had an int array, starting off with the first few primes. For each number check if all primes in the list are divisible, up to a half of the number, if none are, then add it to the list. After a while SCAR will crash, dunno if that was because of a debug box limit, or int array limit.

I wrote one… basically went through all the numbers up to the sqrt of the number. Don't know if that helps you though.

I mean huge prime numbers. Like about fifty zeros after a billion.


Your method might work, but the user will have a number that is generated from the last two digits from the right of the decimal places from a number that is the difference down to billionths of a second between key presses. I take those two numbers and BLANK them to get a more random number… And then make that into a prime, and concantenate it together with others, make the end number a big prime, so forth.

function PrimeNumber(Number : Integer) : Boolean;
var
  Root : Integer;
  NumberFactors : Integer;
begin
  for NumberFactors := 2 to Number - 1 do
    if (Number mod NumberFactors) = 0 then
      Exit;
  Result := True;
end;

There.

Actually, this is better:

function PrimeNumber(Number : Integer) : Boolean;
var
  Root : Integer;
  NumberFactors : Integer;
begin
  Root := Round(Sqrt(Number));
  for NumberFactors := 2 to Root do
    if (Number mod NumberFactors) = 0 then
      Exit;
  Result := True;
end;

This should be faster

function IsPrime(I: Integer): Boolean;
var
  C, CC, Times: Integer;
begin
  if(I mod 2 = 0)then exit;
  if(I mod 3 = 0)then exit;
  C:= 5;
  Times:= Ceil(Ceil(Sqrt(I)) * 1.0 / 2);
  for CC:= 1 to Times do
  begin
    if(I mod C = 0)then exit;
    C:= C + 2;
  end;
  Result:= True;
end;

Also, I found this.

Just found this too.

They both came up as 0 milliseconds…

But are you using a huge number?


I'm talking numbers that are really big… Like up to 4 megabytes, when I devise a way to process it. (Most likely byte by byte…)

Yes…try it yourself.

function PrimeNumber(Number : Integer) : Boolean;
var
  Root : Integer;
  NumberFactors : Integer;
begin
  Root := Round(Sqrt(Number));
  for NumberFactors := 2 to Root do
    if (Number mod NumberFactors) = 0 then
      Exit;
  Result := True;
  WriteLn(IntToStr(GetTimeRunning));
end;

begin
  if PrimeNumber(349876234872398472984754328752340987523423987238479) then
    WriteLn('Prime');
end.

Debug box:

Successfully compiled
0
Prime
Successfully executed

Integers can't be that high. They can only be up to 2147483647. Look at this

program New;
begin
  writeln(inttostr(349876234872398472984754328752340987523423987238479));
end.

yea, Longints can go a lot higher though. In pascal the highest value a long integer can have is 9,223,372,036,854,775,807 but thats still not 4 meg lol. how exactly are you planning to load a 4 meg number into a variable? lol

edit - ah, byte by byte. missed that part.

yea santa has the right idea by doing square root. something like his is the best thing i could come up with, so run with that

man im tired. cant voice my ideas correctly. sorry guys

From: bullzeye95
Integers can't be that high. They can only be up to 2147483647. Look at this

program New;
begin
  writeln(inttostr(349876234872398472984754328752340987523423987238479));
end.

It worked for me…

Try assigning that value to an integer santa and see what happens. I havent done it, but I'm guessing it would either have a cut off point or be set to 0, which would make your result incorrect. Cause an integer physically cant have a value that high.

btw: In your thign santa, shouldnt it be for i := 0 to Root - 1? Cause once it gets up to the root, of course it will divide into itself. :p the rounding would take care of that in most cases, but shouldnt rely on it.

can anyone understand what im saying or am i not making any sense lol? dunno where my head is, im screwed

If I made it root - 1, it would returns numbers such as 121 as prime…

Why is that? I mean do the loop up until (Root - 1), or else you will be checking if the square root of the number divides into the actual number

Aw damn. I messed up my computer memory again. Sorry, meant megabit. So four megabits is about 512 bytes… That sounds better, eh?


Thanks for all of your Ideas, but I realy don't get this argument… Are you talking about negative squares?

From: The Claw
Why is that? I mean do the loop up until (Root - 1), or else you will be checking if the square root of the number divides into the actual number

If I do, for example, the number 121…it would loop through all the numbers from 2 to 10, and 121 isn't divisible by any of those so it would return prime, but 121 is composite…

for I := 2 to Round(Sqrt(121)) + 1 do
  if Round(121 \ I) = (121 \ I) then
  begin
    Result := True;
    Break;
  end;

That's how I'd do it, But you way is better,

for I := 2 to Round(Sqrt(121)) + 1 do
  if (121 mod I) = 0 then
  begin
    Result := True;
    Break;
  end;

Is that work?

i would go for (2^prime number) - 1(those are always a prime number, so you could make everlasting prime numbers:)(scar wont support that lol)

Pow(2, PrimeNumber) - 1?

Is that what you mean killer?

you could have a go at proving the Riemann hypothesis, if its true, you can make a formula for working out the Nth prime number
Riemann hypothesis is the one of the most important unsolved problems, there've mathematicians working on it for 3 centurys, but I'm sure you'll have no problem with it :-)
so it would just work like this

for f:= 1 to f + 1 do
 writeln(inttostr(NthPrime(f)));

I'll have a look now :)

From: Yakman

Riemann hypothesis is the one of the most important unsolved problems, there've mathematicians working on it for 3 centurys, but I'm sure you'll have no problem with it :-)

Yea, but that's just because Ben has been busy lately…

I don't even get the theory of that hypothetis, so I'll just lay back and wait till someone comes up with something.

I made a "IsPrimeNumber"-function some time back, and it's very similar to some of those I see here.

@ R0b0t: What do you even need this for, if I may ask?

-Knives

I need it for making an encryption key.