/sci/ - Science & Math

>>5621294
Every integer greater than 1 can be written as a unique product of primes.

>>5621297
Okay, would it be possible to create an array or list of confirmed primes by testing if an integer is divisible by any of the primes in the list? I don't know if I'm making much sense...it sounds better in my head. But would this be an efficient way to find all prime numbers between 1 and some arbitrary integer n?

>>5621311
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

>>5621311
Yes, actually, I'd say that's the most straight-forward way for finding primes.

>>5621297
* up to permutations

Is this what we are reduced to?
http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

I hope you are in HS or younger OP. This is -literally- fundamental.

>>5621347
There is literally too much to learn, so why does it surprise you that someone might have 'missed' some particular piece of info along the way?

>>5621347
Which is why I said
>This may be an insanely stupid question, but....

I heard the theorem somewhere, but I don't know if I had remembered it right, and I didn't know if there was some stupid thing that broke the theorem or not so I didn't want to make any assumptions without knowing for sure.

Also it was really to get to this question:
>>5621311
but I'm still not sure if there is a more efficient way to check for primality.

>>5621316
This only works up to a point and is not the same thing as I was talking about. It even says on that page that "Trial division" is often confused with the Sieve of Eratosthenes but not the same.

>>5621316

>>5621583
>I'm still not sure if there is a more efficient way to check for primality.
The Sieve of Eratosthenes is efficient up to any number that you are actually going to use.

>This only works up to a point
[citation needed]

>>5621311
I hope you don't mean testing whether a number is prime by seeing whether an integer is divisible by it....non-prime factors exist too...
24 isn't prime, but 48 is divisible by it...

>is it true that every number can be written as a product of prime numbers

No. Not every ring is a UFD.

>>5621916
And since when are elements of rings called "numbers"?

>>5621940
he's just finished abstract algebra 101 so everything is a nail, let him feel clever

>>5621583
>but I'm still not sure if there is a more efficient way to check for primality.

There exist polynomial time algorithms as of 2002. Industry uses probabilistic methods.

Keeping an array of all known primes and cycling through that is just pants on head retarded. How large would your array need to be to check whether an 100 digit integer is prime?

It's only true if you can prove it

>>5621583
Mersenne primes.

>>5621986
formalist detected

>>5621953
>There exist polynomial run-time algorithms for primality testing

[citation needed]

>>5622040
Unless you mean polynomial on the number of bits of n, rather than the actual size of n.

>>5621986

Truth only has meaning within a formal system?

What is the fundamental theorem of arithmetic?

>>5622042

If it's polynomial in the number of bits of n, then a fortiori it's polynomial in the size of n.

And http://en.wikipedia.org/wiki/AKS_primality_test

>>5622048
Yeah, I meant that the other way around. But I found the same article. I did not know this. Factorization is hard, but primality testing appearently isn't.

>>5621986
Fucking moronic.

>>5622052

The general hunch that people have is that factorisation is in P. I've been meaning to waste a summer on that for a while now, but never got around.

>>5622056
Of that, I know that it's false. In fact RSA encryption (amongst other cryptographic functions) rely on that being false.

http://en.wikipedia.org/wiki/Integer_factorization

>>5622066
Although it's subexponential.

>>5622066

Just because RSA relies on it doesn't mean it's difficult. RSA could just be insecure.

Factorisation is not NP-Complete unless NP=coNP, and many researchers believe that it is in fact easy. Just no one found a polynomial time algorithm yet.

>>5622086
Not NP-complete does not imply that it's in P. It's generally believed to be in INP, intermediate NP.

>>5622127

I know, Sherlock. But in the absence of a completeness result there is less ground to argue that factorisation is difficult. The fact that no polynomial time algorithm is known means little - 10 years ago no such algorithm was known for primality. You yourself an hour ago would have argued that primality is difficult.

Even if it was proved that P=NP this doesn't immediately make RSA insecure.

>>5621986
Inb4 Gõdel's incompleteness theorem.

>>5622175
>ply that it's in P. It's generally believed to be in IN

This. Even if an RSA encryption can be cracked in polynomial time, this actually means that it is SLOWER than exponential up until a certain critical value, which may be very large. There is no problem if it is larger than the time any particular RSA-code is in use.

>>5621556
How can you miss something that's taught to 12-year-olds?

>>5622177
Gõdel's incompleteness theorem does NOT say that there are true things that can't be proven. The only way it can be interpreted that way is if there really is a mystical Platonic universe of mathematics where mathematical objects exist in a objective and real form, free from the restrictions of a certain system of logic.
Platonism is as ridiculous as religion.

>>5622186
But it does mean as computers get faster its security drops off quicker.

>>5622197
What do you expect of people who are taught of the magical continuum?

Non-constructive, non-finite mathematics quite simply is religion, pretty much by definition.

>>5622200
This is true, but you can also argue that as computers get faster, RSA-codes are processed faster, and the "safety threshold" will get lower as well. At least I hope so...

>>5622206
Non-finite mathematics? What does that even mean?

>>5622188

fundamental theorem of arithmetic is taught to 12 year olds?

I haven't properly made use of arithmetic since I was 13 years old, so I might have forgotten that.

>>5622245

They deny the reality of infinite sets.

>>5622208

wat

we double the bit length every couple years. if you match it with the bit * core growth curve you have a polynomial*exponential.

>>5621294
> implying prime numbers are the product of two prime numbers
> implying 1 is the product of any prime numbers

>>5622245
non-finite meaning "infinite" e.g. the axiom of infinity, real numbers, and similar nonsense.