Thread for posting tiny primes

[CRGreathouse]

Originally Posted by science_man_88

you say I'm solving for t without proof of that and my statement of the opposite yet you still claim it hence you assume it's true there's the assumption.

I posted a problem for you which, with the variables you're using, requires you to solve for t. You don't have to solve for t -- you could solve for p, or play a game of baseball, or whatever -- but in that case you wouldn't be doing the proposed problem.

[science_man_88]

I don't see a problem asking for t at all actually but do as you want.

[CRGreathouse]

Originally Posted by science_man_88

I don't see a problem asking for t at all actually but do as you want.

Uh... okay?

To clarify, if that's needed: insofar as a person is solving the problem I posed in #618 with your equation, they would solve for t.

[science_man_88]

Originally Posted by CRGreathouse

I was looking for a function that, given a probability p (and N, t, L), would give an n such that

estimatePrimes(N,t,n,L)

is 1 - p.

then this post is flawed as are all after it.

[3.14159]

How would one of you go about proving or disproving the primality of 3379212930002668486657 using only hand calculations? It has no factors under 16777216.

(19:41) gp > Mod(13, 3379212930002668486657)^1689606465001334243328
%73 = Mod(1859858123868907490075, 3379212930002668486657)

Nevermind, the number is composite.

3379212930002668486657 = 30245153 * 111727420588769

Okay, 3773512084578210152449 is at least a PRP. How would you go about in proving it prime, with no computer assistance?

[science_man_88]

I've heard theres a way with subtracting multiples of the divisor you want to check until you either prove or disprove the resultant.

[3.14159]

@Sm88: Too impractical to do a few million times.

The shortest idea I have so far is manually using a few M-R tests.

Or applying Proth's theorem by hand, as the number in question (3773512084578210152449) is a Proth number.

[3.14159]

27009 * 10^20 + 1 = 7^2 * 55120408163265306122449;

55120408163265306122449 is a twin prime.

[CRGreathouse]

Originally Posted by 3.14159

The shortest idea I have so far is manually using a few M-R tests.

I'm not sure how you could use this, by hand, to prove primality. Actually, considering that it's 72 bits, I'm not even sure of how I could use that to prove primality with a computer.

Originally Posted by 3.14159

Or applying Proth's theorem by hand, as the number in question (3773512084578210152449) is a Proth number.

That's probably the most reasonable way. It would be a pain, though.

[3.14159]

Originally Posted by Charles

I'm not sure how you could use this, by hand, to prove primality. Actually, considering that it's 72 bits, I'm not even sure of how I could use that to prove primality with a computer.

About 20-25 tests prove that it is prime. Oh, right.. M-R's weakness = Proth numbers.

You can prove any non-Proth 72-bit number prime with M-R.

Ex:

(21:29) gp > ispseudoprime(8183202143983816686553, 30)
%130 = 1

That was a 72-bit number.

Originally Posted by Charles

That's probably the most reasonable way. It would be a pain, though.

It depends on a. Suppose a = 23;

23^1886756042289105076224 modulo 3773512084578210152449?

Multiplication of 23 by itself has to happen at least 16 times for it to be ≥ 3773512084578210152449.

Also, a good idea would be to identify when the mod results repeat. (If they do repeat.)

Ex: Powers of 71, mod 23: 2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1, 2, 4, 8, 16, 9, 18, ...

[3.14159]

6^134217728 + 1 is divisible by 51808043009.

Two factors for 5^36893488147419103232 + 1: 221360928884514619393 and 2434970217729660813313 both divide 5^36893488147419103232 + 1.

Probably well-known at the moment;

I betcha no one can find the smallest divisor of 10000^(2^160) + 1, which = 10^(2^162) + 1.