Ghideon

So you do not know? Not even a rough estimate? So you do not know? Not even a rough estimate? RSA-260?

In your example; how many numbers do you need to store?

Can you present an example, how is Euclid used in your method? How it is related to your " multiplying by 5"?

I'll try again, providing different answers since the questions are different There exists many algorithms to factor semi primes. I have to assume that "reliable" means "deterministic" in contrast to probabilistic. An example is trial division; for any given semi prime n=p*q (p and q primes) trial division will always find the factors. It is 100% reliable; there are to semi primes n where the algorithm produces incorrect factors*. GNFS is another algoritm.** A semi prime is the product of two primes. Finding semiprimes can be done by iterating through lists of prime numbers and multiplying them. That is again a different question. Trial division and GNFS have no upper bounds; any finite semiprime can be factored by the algorithms. It does not matter if the semiprime is large, the algorithms will eventually terminate and produce the correct factors. Then of course is the practical question; how you define "large", can large semipimes be factored given available resources (time and computing power). Factoring a semiprime that is the product of two large primes of similar sizes is inefficient and practically impossible if n is large enough. How this is related to your idea about multiplication and working with 5*n i have no clue. The cartoon still explains the situation. *) of course assuming algorithm execution is correct. **) General Number Field Sieve; the most efficient currently known algorithm for factoring

What do you mean by find semiprimes?

Your ideas about prime numbers may have some use in a work of fiction, poetry or similar. Or maybe in computer education; "find one major flaw in this attempt at an algorithm (correct answer: the unnecessary multiplication)"? In mathematics, where this is posted, I fail to find your ideas about primes useful. What if? As I said above: There are many reliable methods for factoring semiprimes.

Introduction to AI usage for legal professionals. Your example is interesting because it is easy to relate to and also opens for multiple lines of reasoning about generative AI. 1: We know an answer exists; the episode do exist and it has music. But it may or may not be included in the training data for the model. The music may be unreleased 2: There are many different ways to search for the answer, depending on what one knows about the episode, the music or other details that allows a model to infer an answer. Multimodality comes into play; does the model infer the answer from text only, or also audio and video? 3: If the model inference fails; what does it output? In the context of this thread (and in my presentation) is the response "intelligent" or at least useful? 4: Context; how does the level of detail provided to the model affect the answer. Note: In this specific case I did a quick test and it failed to find the music even with web search enabled. But I got a possibly useful explanation of why it failed* and a suggestion**. *) Short extract: custom/production-library needle-drop (or bespoke cue) cleared for the episode but not commercially released. *) contact the musical supervisors. (The AI got the names from the credits of the episode)

Not necessarily a bad analogy but logically it works only if you already know that the original number (let's call it n) is prime (and hence have no need for a test)? If n is semiprime the multiplication results in a larger composite making the test slower than running the (hypothetical) algorithm on n. Also note the state of the art algorithms for primality tests are extremely fast compared to composite (or semi prime) tests. (I resented comparisons in an earlier post) It would certainly be of interest in cryptography? Since for instance RSA build on the fact that testing for prime is easy compared to factoring.

May I ask what you used as input in your searches? (Curious; it may be an useful example in a work-related presentation)

The above makes sense. The rest does not. Take a look at the cartoon I posted.

Hello! Maybe, it depends on what you would like help with. The title "Black hole Paradox Solved!" sounds like a claim rather than a question?

Correct about what? "isn’t always necessary" is wrong,"is never useful"* would be correct if referring to anything I said. Anyway, please demonstrate one case when a composite number made lager is necessary*. That would prove me wrong? Yes that follows from the definition, so that is correct. The rest makes no sense. *) in the context of this thread, primality test, of course.

Why 5? I assume it is a random prime since you haven't described any method. 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. 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.

@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...)

@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: (emphasis mine) Yes, that's where I come from; the practical implications of managing keys and certificates, increased in 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.

Quick question, am I misunderstanding something? spoiler Isn't 2833×3527=9991991 ?

No, what you have described is not useful. 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 pseudo prime) RSA-240 took about 1000 core years 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: (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.

multiplication does not add information about 11. Did you mean "division" instad of multiplication? 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.

That sentence seems kind of odd? This is the first time you mention Twin Primes so I do not know how it is related to previous discussion. Yes, it follows form elementary modular arithmetics? I might be able to produce a mathematical proof if it's helpful.

Have you compared your ideas with observations such as GW170817? the merger happened 140 million light years away. https://dcc.ligo.org/public/0145/P1700294/007/ApJL-MMAP-171017.pdf

Here are some illustrations of a sieve algoritm visualised in a grid with 6 columns. First the final result: natural numbers n<300 with primes marked in green. The list of primes is the result of running the sieve of Eratosthenes for n<300. Illustration of the starting point of the algorithm; we use grid cells without numbers for this illustration. We will run the standard algorithm by counting the grid cells and count how many cells to skip rather than looking at numbers in the grid. Count grid cells from top left (first cell = 0) and mark every second cell with a count > 2. I guess this could qualify as a "pattern" since it forms coloured stripes of marked cells? Note again that this is basically sieve of Eratosthenes, just without any optimisations. Nothing special. Start from the beginning and count past the blue bordered cell until an unmarked cell is found. You will count 0,1,2,3. Mark every 3rd cell after cell no 3. We now have two unmarked columns. If the cells were numbered these cells would cover the all numbers 6k+1 and 6k-1 used in a 2,3 wheel. Again this is standard except for the start; we would skip ahead to p2 (cell 32=9 in this case) in the standard algorithm Note! the illustration is unclear; The blue border around cell 2 has disappeared. Starting from the top again: first empty cell after the previous blue framed one is 5. This time, when we count cells 5,10,15,... it looks like some kind of diagonals. Note that we revisit some grid cells; I mark them again to show that some kind of "pattern" appears. If we continue like there will be alternating "patterns" that becomes sparser as the count of the starting cell grows. The final result before we put numbers in the cells. By numbering from top left starting with 0 every white cell will contain primes and every pink cell will contain composite numbers.This is of course nothing new or any patterns in prime numbers, it's just a consequence of expressing the well known sieve an visualising in a grid. This is how I see a connection between the sieve of Eratosthenes, wheel optimisation and what someone may see as "patterns" during the execution of the algorithm. As a reference; the complete set of illustrations in an animation. Note that without any optimisation we do not cut off at sort(n) meaning there is a lot of unnecessary work in later steps. I kept these as an illustration. In the end of the animation the numbers with primes highlighted will flash by before restarting. See the first picture above for a freeze of that frame. It was a little tricky to get this right, hopefully there are no major mistakes.

d The program does not seem complete but it helps; it still looks like the classic Sieve of Eratosthenes + optimisation. I thought about this; let's analyse from a different angle. A sieve is a step-by-step procedure systematically crossing out composite numbers. You don’t have to “test” each number for primality but loop over small primes and mark their multiples. For example, when on p=5, marking 10,15,20,25,… only hits composites; same idea for p=7,11,… Each pass begins from the next unmarked integer; in a sieve that guarantees its prime (if it were composite, a smaller prime factor would already have crossed it out). This is the basic idea of the classic Sieve of Eratosthenes as far as I know (without any optimisations that seems to be part of the idea in OP). But now; if the implement the the classic Sieve of Eratosthenes, and just look at the output. I mean how Sieve of Eratosthenes graphically looks like; is there anything that looks like "patterns"? And if so, are these "patterns" what you use in your idea? If this long-shot is correct then we may be looking at the same algorithm but from different angles; you are reverse engineering the Sieve of Eratosthenes from observation of what it "looks like". I might try to create an illustration of this.

The idea is about sieving; you mark all non primes in a list of integers 0..n which leaves you with a list of the prime numbers <= n. In a sieve approach you do not test a number for primality, you remove non-primes by some algorithm until you have only prime numbers.

Ok; to avoid further contradictions in your descriptions, maybe start form scratch: Describe the algorithm of your sieve idea. Be detailed so that someone that does not yet know your idea can follow the algorithm and check that it produces a list of prime numbers smaller than some natural number "n". This could be performed with pen and paper (for small n) or programmed for larger values of n. Once the algorithm is clearly described we can see if it works for any n, if it is identical or similar to known methods and, if interesting, analyse time and memory complexity.

That is one use of wheel factorisation. If you scroll down on the wikipedia page* you will find: Trial division is of less importance in this discussion; you have asked about a sieve idea of yours. That seems to contradict what you have described so far; your opening post states that you use the set of values: Which means that you work with numbers co-prime to 6. Also, you refer to a set of values to mark non-primes: You still have not commented on O(n log log n) time with O(n) space; have you compared your algorithm to wheel optimization and Eratosthenes sieve; the one I compare to your description of your idea? If you do not know how to compare, just post a question. https://en.m.wikipedia.org/wiki/Wheel_factorization