I was looking at the 6x-+1 thread and I agree with Studiot that he still needs a test for Primes to simplify the computation.

I was unaware of the 6x+-1 and I don’t want to hijack his thread. But to test for Primility could you multiply the number in question by any known Prime number and see if the product is only divisible by those numbers?

I mean you already know the Prime factor you used. If in doubt test with another known Prime.

If 6x+1 describes all Prime numbers, it is not a sieve you need but a test for Prime numbers to complete the computation problem.

I know it sounds too simplistic. But has anyone heard of it before? If I am wrong just ignore. I just didn’t want to distract from the other thread.

3 hours ago, Trurl said:

I was looking at the 6x-+1 thread and I agree with Studiot that he still needs a test for Primes to simplify the computation.

I was unaware of the 6x+-1 and I don’t want to hijack his thread. But to test for Primility could you multiply the number in question by any known Prime number and see if the product is only divisible by those numbers?

I mean you already know the Prime factor you used. If in doubt test with another known Prime.

If 6x+1 describes all Prime numbers, it is not a sieve you need but a test for Prime numbers to complete the computation problem.

I know it sounds too simplistic. But has anyone heard of it before? If I am wrong just ignore. I just didn’t want to distract from the other thread.

One of the problems is the variability of the ocurrence of primes.

Here is a comments from the beginning of du Sautoy's book.

Here are the primes amongst the 100 numbers either side of 10,000,000

First those below 10,000,000

9,999,901 9,999,907 9,999,929 9,999,931 9,999,937 9,999,943 9,999,971 9,999,973 9,999,971

But now look how few there are in the numbers above 10 million

10,000,019 10,000,079

The only guaranteed test I know of is to keep an ever growing list of primes, starting with 2.

Clearly your test rquirement will be for a number X larger than the largest prime on your list.

So starting with 2 successively divide primes from your list into X

If no prime on your list divides into X ( ie there is zero remainder) then continue dividing odd numbers greater than your largest prime but less than X until you reach X itself.

If none of these numbers divides X then X is prime.

Well my figuring is to take 5 or any other and multiply it by the number in question of being prime.

So if you were determining if 11 was Prime you’d multiply it by a known Prime say 5.

You get 55 which is not Prime but a semi prime.

But is it as difficult as determining Prime to prove semi prime? With lager numbers it may work easily for some numbers but harder to prove it semi prime? But any factor that isn’t Prime would break down into smaller Prime factors.

I just brought this up because I agree with you the 6x+-1 is to heavily computational without a Prime number test.

You said that all Primes can be expressed by 6x+-1 but computing in series some pairs are false positives. Without a test for Primes doesn’t this throw a monkey wrench into the series?

My question is: is it easier to prove a number is semi prime than prime?

Just for the fact it is no longer prime? And non prime factors are easier to factor.

17 hours ago, Trurl said:

So if you were determining if 11 was Prime you’d multiply it by a known Prime say 5.

multiplication does not add information about 11. Did you mean "division" instad of multiplication?

17 hours ago, Trurl said:

My question is: is it easier to prove a number is semi prime than prime?

As far as I know it is harder. Primality testing (is N prime?) algorithms outperforms best algorithms for semiprimality testing (is N the product of exactly two primes?) as far as I know.

4 hours ago, Ghideon said:

multiplication does not add information about 11. Did you mean "division" instad of multiplication?

No I mean multiplication. If the number in question is Prime then multiplying it by a known Prime would create a semi prime.

If the number in question isn’t Prime a semi prime wouldn’t be produced. I’m saying the non semi prime should be easier to factor then testing if the original number was Prime.

A semi prime may be more difficult to factor, but if you multiply the test prime by a number that isn’t Prime the factorization should be trival. (maybe)

So if 12 was tested to be Prime, we multiply it by 5 a known Prime number. 60

Sixty on the sieve is not Prime.

2*2*3*5

Not a semi prime thus not prime.

Obviously we need bigger numbers. But I think it may be useful if applied to the sieve.

If not no big deal just another abstract thought.

9 hours ago, Trurl said:

No I mean multiplication. If the number in question is Prime then multiplying it by a known Prime would create a semi prime.

If the number in question isn’t Prime a semi prime wouldn’t be produced. I’m saying the non semi prime should be easier to factor then testing if the original number was Prime.

A semi prime may be more difficult to factor, but if you multiply the test prime by a number that isn’t Prime the factorization should be trival. (maybe)

So if 12 was tested to be Prime, we multiply it by 5 a known Prime number. 60

Sixty on the sieve is not Prime.

2*2*3*5

Not a semi prime thus not prime.

Obviously we need bigger numbers. But I think it may be useful if applied to the sieve.

If not no big deal just another abstract thought.

So how would that work with say this number

9,991,991

17 hours ago, Trurl said:

But I think it may be useful if applied to the sieve.

No, what you have described is not useful.

17 hours ago, Trurl said:

. I’m saying the non semi prime should be easier to factor then testing if the original number was Prime.

Quite the opposite; factoring a semi prime n is harder than testing if n is prime. for a realistic number in cryptography the difference is huge; many orders of magnitudes. Example: Factoring (verifying semi prime) RSA-240 took about 1000 core years

The total cost of our computation is about 1000 core-years for RSA-240

https://arxiv.org/pdf/2006.06197

By comparison; using ECPP to prove that RSA-240 is not prime takes <1s on a consumer laptop (MacbookPro m1). The procedure I used to do a quick test to get a ballpark number:

gp
isprime(124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099,3)

(installation on Apple can be done via Home Brew: brew install gmp-ecpp)

For a more formal comparison we could check the time complexity of GNFS vs ECCP algorithms. My angle is more practical engineering/cryptography/computing, so for any in-depth mathematically rigorous treatment I would refer to @studiot.

Edited September 3Sep 3 by Ghideon
correction; semi prime, incorrectly used "pseudo prime"

Well I’m not saying a semi prime is easier to factor.

I’m saying the number in question is not Prime, multiplying it by a known Prime will not result in a semi prime and thus easier to factor.

If both numbers are Prime there will be a difficult semiPrime to factor. You could check by trying the process again with a different Prime number multiple.

I test it with 9,991,991 It is difficult to factor. I multiplied by 5, 23, and 7

First look I’d say it was Prime because it ends in 5 and the 49,959,955 is difficult to factor.

9,991,991*36=359,711,676 not prime. That is just a random Prime number. That shows nothing. Just an illustration of 9,991,991 wasn’t Prime it might be easier to factor the product of a prime and non Prime.

I need some time to look at this further.

But a shoutout to @studiot can you see what I was attempting to do?

5 hours ago, Trurl said:

I test it with 9,991,991 It is difficult to factor. I multiplied by 5, 23, and 7

First look I’d say it was Prime because it ends in 5 and the 49,959,955 is difficult to factor.

What I had in mind was you to demonstrate your multiplication test in full.

All numbers greater than 5, that end end 5, are non prime since all are diisible by 5.

In fact that is another way of shortening my test.

But why 5,23 and 7 (in that order ?) ?

Your guess is correct 9,991,991 is prime but your last line should be something like

therefore 9,991,991 is prime.

this is actually a better number for a prime test.

156,423,343

Edited September 4Sep 4 by studiot

15 hours ago, studiot said:

But why 5,23 and 7 (in that order ?) ?

Well they are in no order. I multiplied by 5 and could factor the result easily (not at all). So far a second test I tied implying 9,991,991 by 23 and again tried to factor the product with no success. I repeated the multiplication of 9,991,991 by 7 and could not factor it either.

I chose the Prime multiple randomly. I was on my phone so I wanted to keep it small.

My logic is this:

Number in question if it is Prime multiplied by known Prime results in Prime times Prime

Or semi Prime (which I won’t be able to factor)

And this means both numbers that were multiplied are Prime

—-——————————————————————

But if the number in question is not a Prime number the multiplication with the known Prime will result in a composite number that should be easier to factor (and it helps simplify the knowledge gained by the sieve)

______-_

So basically it is just multiplying by a Prime and factoring the product to work around division of N by every smaller number.

I don’t know how useful it is or that it works all the time. Or why Guass didn’t mention it because he didn’t have a computer and was doing arithmetic by hand. But as Ghideon mentioned that semiPrimes are even more difficult to factor. But there is no factoring of semiPrimes (other than difficult in that the formed semiPrimes have no other factors) .

If this work and proves useful (which it hasn’t yet), this “math hack” could speed up many of number crunching.

To me the main weakness is the difficulty of factoring the semiPrime like Ghideon said, but the sieve information should help. And the factoring that results in a composite number should be relatively easy.

That all kind of sounds like putting on a backpack full of rocks, weighing myself, then subtracting the backpack to find my own weight.

Exactly how is finding the factors of a semi prime (then checking if the one non trivial factor is prime) easier than just finding the factors of the original number?

Edited September 5Sep 5 by pzkpfw

7 hours ago, Trurl said:

So basically it is just multiplying by a Prime and factoring the product to work around division of N by every smaller number.

So did you manage to factor 156,423,343 ?

Doing this or not is a good test of a method.

On 9/4/2025 at 10:50 AM, studiot said:

Your guess is correct 9,991,991 is prime

Quick question, am I misunderstanding something?

spoiler

Isn't 2833×3527=9991991 ?

in general in computer science, prime verification (or decision) problem can be solved in polynomial time.
https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

I would still call it as intermediate polynomial problem.

3 hours ago, Ghideon said:

Quick question, am I misunderstanding something?

spoiler

Isn't 2833×3527=9991991 ?

Gosh yes you are absolutely correct, I miscopied it I should have written 9.999,991 (which is the largest prime number less than 10 million)

Thanks +1

18 hours ago, studiot said:

So did you manage to factor 156,423,343 ?

Remember I am not factoring but testing for primality.

So again I multiply 156,423,343 by 5 and get 782,116,715 which according to my rules is semiPrime. So 156,423,343 is Prime.

I didn’t cheat and thought you may have given me a counter example. But if were to try and factor I would start on the right side of the digits. For 782,116,715 I would start on the right with what factors would go into 15. (3 & 5 )

7-3 =4

__—//////

But I’m not sure dividing right to left will factor, but as far as I know the number is prime. If the given number was semiPrime to start multiplying it by 5 should produce a composite number.

I would have to write it up. I don’t have time tonight. I have made posts about prime testing and factoring semiPrimes. However those problems are not the path I was steering towards on this thread.

5 hours ago, Trurl said:

So again I multiply 156,423,343 by 5 and get 782,116,715 which according to my rules is semiPrime. So 156,423,343 is Prime.

Unlike the first number I misquoted, where I made a silly copying mistake 156,423,343 is not prime.

156,423,343 = the product of two primes 22,343 x 7001.

I should have constructed this example in the first place as it is beginning to show just how far you might have to go to find any factors.

This of course is also beginning to demonstrate the interest in large or very large primes for cryptography.

To recap

Apologies for the earlier mistake

9,991,991 is not prime and = 2833×3527

9,999,991 is prime .

@Trurl You have been provided answers and arguments backed by references to scientific papers and by some quick, reproducible tests from software engineering perspective. How come you keep ignoring this? I see no science in your answers.

Instead of a reference to established computer science let's try a cartoon this time:

Member:-I need to find a needle in this haystack... if there is one, I'm not sure.

Trurl: -I have an idea, let's add more hay. Once you have 5 times as much hay it should, logically, be easier to find the needle in the original haystack!

Member: -WTF??? How is this going to help??

Side note:

52 minutes ago, studiot said:

This of course is also beginning to demonstrate the interest in large or very large primes for cryptography.

(emphasis mine)
Yes, that's where I come from; the practical implications of managing keys and certificates, increased computing power available to adversaries, bugs in implementations, scientific progress, changing of standards... I have an interest in the mathematics but my main experiences are from the engineering side; nice to see your posts; helps me see other perspectives.

Edited September 6Sep 6 by Ghideon
spelling

Why has there been no mention of Fermat's little theorem in this thread?

[BTW, I have a personal interest in Fermat's little theorem because I independently discovered this theorem 33 years ago. At the time, I thought I had discovered something truly remarkable. Fortunately, it wasn't too long afterwards that I found the theorem called "Fermat's little theorem" in a mathematics dictionary. I discovered it by exploring the decimal expansion of 1/p for prime number p, investigating the length of the repeated sequence of digits. For example, for p=7, the repeated sequence 142857 has length 6 and 142857x7=999999.]

On 9/6/2025 at 5:56 AM, Ghideon said:

Instead of a reference to established computer science let's try a cartoon this time:

No I am just biased because it is my method. But as KJW said even Fermat’s prime test has liars.

Prime *Prime *Prime should always equal a composite but even * 5 can be hard to find factors.

I know it sounds stupid in application: multiple by five and see what you get.

I don’t always approach math scientifically. Sometimes intuitively. The Prime by prime equals semiPrime I don’t think is a complex thought. That is to be not tried before. It is just a fast observation.

On 9/3/2025 at 4:18 PM, Ghideon said:

For a more formal comparison we could check the time complexity of GNFS vs ECCP algorithms.

I will have to research these algorithms. I have never used them. I have tried to avoid Primes. I tried to study circuits and amateur radio. Something more tangible. But here I am again attempting to do data science.

But you are right that I don’t always use the scientific method. To me finding Primes in a series is misleading. Greater minds than us have tried and failed. My odometer hit 116811 then 116816 then 116818. Suppose I was looking to find 2 pairs of matching numbers. These would be easy to see but difficult if I tried to find an equation that described when this occurs in sequence from zero to 116828.

I mention this because I think prime numbers share the same elusive behavior. Mathematicians look at them and see patterns that aren’t there or see chaos.

On 9/6/2025 at 5:03 AM, Trurl said:

Remember I am not factoring but testing for primality.

@Trurl When you apply your "method" or "idea" to test for primality it looks like you start with multiplication by some number; given an initial number n you multiply n with some number m to get n*m and then work from there, correct*?

Here are three numbers 4829995653 and 8049992755, 1220703125.
-What is the first number you multiply with when testing those for primality?
-Why do you multiply with that number? Is it a random choice?

(* The ideas makes no sense to me but lets see where this goes...)

It will take me some time to write this up but I will test one of your numbers with the calculator on my phone.

Say we don’t know if 4829995653 is Prime, semiPrime, or composite.

Then we multiply it by a known Prime. I usually start with 5.

5* 4829995653 =24149978265

This product is now either semiPrime or composite.

But trial and error we find

24149978265 / 3 =8,049,992,755

So the product was semiPrime it is composite, so unknown number times known Prime is composite so the unknown number is composite.

———

Very simple. May or not prove useful. But if you are dealing with a sieve, the sieve is practically doing the same simple process. But the only difference is this is jumping to steps that would occur in the future of the sieve.

This is just a tool. It doesn’t always simplify the process. Like you said Prime times Prime gives a semiPrime that isn’t always verified easily. And if the unknown number is already a semiPrime the product still could be difficult to factor.

I don’t know how useful it is, but what if you were completely your sieve in both the present and future numbers.

14 hours ago, Trurl said:

Say we don’t know if 4829995653 is Prime, semiPrime, or composite.

Then we multiply it by a known Prime. I usually start with 5.

5* 4829995653 =24149978265

Why 5? I assume it is a random prime since you haven't described any method.

15 hours ago, Trurl said:

But trial and error we find 24149978265 / 3 =8,049,992,755

But your multiplication means you have a larger number, more digits than the number I gave you. That means you* are guaranteed to do more work. Your "method" does not make any sense.

3 is of course one factor of 5*4829995653, because 3 is a factor** of the original number 4829995653. Any sane method would find that without adding the unnecessary extra work of multiplication.

16 hours ago, Trurl said:

But if you are dealing with a sieve, the sieve is practically doing the same simple process. But the only difference is this is jumping to steps that would occur in the future of the sieve.

No. A prime number sieve does not include trial division. A sieve uses a systematic, deterministic method to eliminate composite (non-prime) numbers, you describe something completely different.

*) The same holds for a calculator or computer running an algorithm that follows the described idea
**) Because I deliberately used 3 as a factor in the number, to prove my point.

18 hours ago, Ghideon said:

Why 5? I assume it is a random prime since you haven't described any method.

On 9/10/2025 at 3:13 PM, Ghideon said:

*) The same holds for a calculator or computer running an algorithm that follows the described idea
**) Because I deliberately used 3 as a factor in the number, to prove my point.

You are correct a composite number made lager isn’t always necessary. But if that number is so large that you can’t factor it, multiplying it by a Prime number may change the perspective and create more factors.

But I am concerned with Prime numbers. A Prime times a Prime is a semiPrime. If I suspect that a number is Prime and it is so large I can’t factor it maybe I can determine if its product is a semiPrime.

Yes it can lead to larger numbers but it may be the only information you can get about the number. My method is not rocket science. It is a simple observation. I was not high when I thought of it.

I may have increased the magnitude of the number (relatively small) but I have also increased the number of factors.

But the method would prove more useful if there was a reliable method to factor semiPrimes.

And my question to you is why sieve Primes and not keep track of the semiPrimes at the same time?

But I welcome your challenge.

It is only an idea until someone tests it.