Timeline for Taking pairwise coprime integers from prescribed sets
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 9, 2018 at 7:18 | comment | added | Turbo | Please answer my question. Do you know the complexity of choosing a probable prime? Are you aware of polymath project on deterministic selection of primes? Please take a look. The last point you mention is the most relevant. | |
| Oct 9, 2018 at 6:21 | history | edited | Aaron Meyerowitz | CC BY-SA 4.0 |
added 1666 characters in body
|
| Oct 9, 2018 at 3:46 | comment | added | Aaron Meyerowitz | To find $m$ pairwise relatively prime $n$ bit integers is not hard for manageable size $m.$ For $m=1$ anything will do. For $m=3$ use $\{2^n+j \mid j=1,2,3\}.$ Instead of primes take probable primes (or numbers with no small prime factors) and just check gcds. Or find $km$ primes each with $n/k$ bits and take products. | |
| Oct 9, 2018 at 0:49 | comment | added | Turbo | What is the complexity of picking one prime of $m$ bits? | |
| Oct 8, 2018 at 20:04 | comment | added | Aaron Meyerowitz | OK, I made it less vague. | |
| Oct 8, 2018 at 20:03 | history | edited | Aaron Meyerowitz | CC BY-SA 4.0 |
added 301 characters in body
|
| Oct 8, 2018 at 7:47 | comment | added | Turbo | There are so many issues with this obvious answer that everyone is first aware of 1. What is the gap between primes? 2. What is the complexity of choosing a prime? 3. What is the gap between coprime versus gap between prime numbers? 4. It is easier to choose two coprimes in $m+1$ time complexity while it is unclear how to choose even two primes and many other issues such as not quantifying 'might be as good as it gets'. | |
| Oct 7, 2018 at 14:55 | history | answered | Aaron Meyerowitz | CC BY-SA 4.0 |