Asdf at 00:05, 20 August 2009

2009-08-20T00:05:42Z

← Older revision		Revision as of 17:05, 19 August 2009
Line 1:		Line 1:
	We'll use the term "generic prime" to denote a prime with high [[Kolmogorov complexity]], e.g. a k-digit prime with complexity at least <math>\sqrt{k}</math>. Note that almost all primes are generic.		We'll use the term '''generic prime''' to denote a prime with high [[Kolmogorov complexity]], e.g. a k-digit prime with complexity at least <math>\sqrt{k}</math>. Note that almost all primes are generic.

	On the other hand, the [[finding primes]] conjecture is false for generic primes, as deterministic algorithms in poly(k) time can only produce numbers of complexity <math>O(\log k)</math>. Thus any solution of this conjecture must in some way distinguish primes from generic primes. This rules out any approach based purely on average-case results about the distribution of primes, since primes and generic primes are essentially indistinguishable in these results. (However, for the purposes of the weak conjecture, one could hope to use average-case results on relatively thin sets, of size <math>10^{\varepsilon k}</math> or so.)		On the other hand, the [[finding primes]] conjecture is false for generic primes, as deterministic algorithms in poly(k) time can only produce numbers of complexity <math>O(\log k)</math>. Thus any solution of this conjecture must in some way distinguish primes from generic primes. This rules out any approach based purely on average-case results about the distribution of primes, since primes and generic primes are essentially indistinguishable in these results. (However, for the purposes of the weak conjecture, one could hope to use average-case results on relatively thin sets, of size <math>10^{\varepsilon k}</math> or so.)

	A factoring oracle breaks the indistinguishability between primes and generic primes, since non-generic primes cannot be given any non-trivial factoring. So generic primes do not seem to provide an obstruction to the conjecture with factoring.		A factoring oracle breaks the indistinguishability between primes and generic primes, since non-generic primes cannot be given any non-trivial factoring. So generic primes do not seem to provide an obstruction to the conjecture with factoring.

Teorth: New page: We'll use the term "generic prime" to denote a prime with high Kolmogorov complexity, e.g. a k-digit prime with complexity at least $\sqrt{k}$ . Note that almost all primes ...

2009-08-05T01:45:45Z

New page: We'll use the term "generic prime" to denote a prime with high Kolmogorov complexity, e.g. a k-digit prime with complexity at least <math>\sqrt{k}</math>. Note that almost all primes ...

New page

We'll use the term "generic prime" to denote a prime with high [[Kolmogorov complexity]], e.g. a k-digit prime with complexity at least <math>\sqrt{k}</math>. Note that almost all primes are generic.

On the other hand, the [[finding primes]] conjecture is false for generic primes, as deterministic algorithms in poly(k) time can only produce numbers of complexity <math>O(\log k)</math>. Thus any solution of this conjecture must in some way distinguish primes from generic primes. This rules out any approach based purely on average-case results about the distribution of primes, since primes and generic primes are essentially indistinguishable in these results. (However, for the purposes of the weak conjecture, one could hope to use average-case results on relatively thin sets, of size <math>10^{\varepsilon k}</math> or so.)

A factoring oracle breaks the indistinguishability between primes and generic primes, since non-generic primes cannot be given any non-trivial factoring. So generic primes do not seem to provide an obstruction to the conjecture with factoring.

Generic prime - Revision history

Asdf at 00:05, 20 August 2009

Teorth: New page: We'll use the term "generic prime" to denote a prime with high Kolmogorov complexity, e.g. a k-digit prime with complexity at least \sqrt{k}. Note that almost all primes ...

Teorth: New page: We'll use the term "generic prime" to denote a prime with high Kolmogorov complexity, e.g. a k-digit prime with complexity at least $\sqrt{k}$ . Note that almost all primes ...