Forum: Math
2008-03-22, 19:52
|
|
Replies: 15
Views: 1,813
Since this question deals with subset sums I...
Since this question deals with subset sums I might as well as this here...
Is it easier to solve subset sum problems whose sets can be partitioned into two, similarly sized, super increasing sets....
|
|
Forum: Math
2008-03-07, 16:14
|
|
Replies: 15
Views: 1,813
|
|
Forum: Math
2008-03-06, 03:39
|
|
Replies: 15
Views: 1,813
|
|
Forum: Math
2008-03-05, 23:47
|
|
Replies: 15
Views: 1,813
Modular Subset "Product" Problem
Is there info on how to solve this type of problem somewhere?
Suppose you have a set of congruences A[i] mod B[i] such that A[i] is a random integer and B[i] is a random prime. (the primes are...
|
|
Forum: Miscellaneous Math
2007-12-15, 19:59
|
|
Replies: 10
Views: 2,177
|
|
Forum: Miscellaneous Math
2007-12-15, 14:12
|
|
Replies: 10
Views: 2,177
|
|
Forum: Miscellaneous Math
2007-12-15, 12:50
|
|
Replies: 10
Views: 2,177
|
|
Forum: Miscellaneous Math
2007-12-15, 10:18
|
|
Replies: 10
Views: 2,177
New Multiplication Algorithm
I just coded a new multiplication algorithm which slower than trial multiplication :smile:
It is in java code.
import java.math.BigInteger;
import java.util.ArrayList;
import...
|
|
Forum: Math
2007-12-07, 22:35
|
|
Replies: 10
Views: 1,144
I answered that already. You just have to check...
I answered that already. You just have to check whether p-1 is an element generated by 2^x mod p. Also, since p-1 is a special case of being -1 mod p you don't even have to compute the order of p-1...
|
|
Forum: Math
2007-12-07, 18:18
|
|
Replies: 10
Views: 1,144
I think that to prove that a particular prime...
I think that to prove that a particular prime will never divide 2^n+1 you need to show that 2^n+1 mod p never equals 0. Or that 2^n mod p is never equal to p-1. So if p-1 is never generated by base...
|
|
Forum: Math
2007-12-02, 10:26
|
|
Replies: 9
Views: 1,434
3^4 mod 11=5; ord(3)=5;
3rd root inverting...
3^4 mod 11=5; ord(3)=5;
3rd root inverting exponent= 3*exponent=1 mod 5, inverting exponent=2;
so (3^2)^4 =5^2 mod 11;
therefore 9^x = 3 mod 11;
and 3^x = 5 mod 11;
also ord(9)=5;
So...
|
|
Forum: Math
2007-12-02, 02:40
|
|
Replies: 9
Views: 1,434
Yeah I realized this couple of minutes after...
Yeah I realized this couple of minutes after posting. A correct simplification is that ord(b) must be divisible ord(a) without leaving a remainder.
Anyway it turned out that this did not help...
|
|
Forum: Miscellaneous Math
2007-12-01, 14:43
|
|
Replies: 5
Views: 1,695
|
|
Forum: Miscellaneous Math
2007-11-30, 13:32
|
|
Replies: 5
Views: 1,695
see:...
see: http://www.research.att.com/~njas/sequences/table?a=1358&fmt=5
The proof can be made deterministic by using theorem 3 from http://arxiv.org/PS_cache/math/pdf/0506/0506067v1.pdf
Using it the...
|
|
Forum: Math
2007-11-30, 13:18
|
|
Replies: 9
Views: 1,434
"Hence ord(a)|ord(b) is a necessary and...
"Hence ord(a)|ord(b) is a necessary and sufficient condition that there is a k so that bk = a in a cyclic group."
So, in other words, if the order of the element is greater than the order of the...
|
|
Forum: Miscellaneous Math
2007-11-30, 11:38
|
|
Replies: 5
Views: 1,695
Proof of Goldbach Conjecture
I think I proved the Goldbach conjecture, here is proof:
This conjecture states that every even number greater than 2 can be expressed as the sum of two primes.
This conjecture can be restated...
|
|
Forum: Math
2007-11-27, 18:01
|
|
Replies: 9
Views: 1,434
|
|
Forum: Factoring
2007-11-21, 21:51
|
|
Replies: 2
Views: 1,080
|
|
Forum: Miscellaneous Math
2007-11-20, 18:14
|
|
Replies: 3
Views: 1,300
|
|
Forum: Miscellaneous Math
2007-11-20, 03:14
|
|
Replies: 3
Views: 1,300
Finding totient using discrete logarithm
I am posting this here because I think there might be a serious flaw with this technique. Given composite N, generator g, and prime q. find a generator g that is a primitive root to a composite N...
|
|
Forum: GMP-ECM
2007-11-16, 00:30
|
|
Replies: 8
Views: 1,832
I factored 2^3000-1 and found a factor of 71...
I factored 2^3000-1 and found a factor of 71 digits (8877945148742945001146041439025147034098690503591013177336356694416517527310181938001) How can I check if this is a new factor? In 2^20000-1 I...
|
|
Forum: Math
2007-11-14, 16:07
|
|
Replies: 7
Views: 1,171
|
|
Forum: Math
2007-11-13, 15:35
|
|
Replies: 7
Views: 1,171
"For a given prime p, there are not very many...
"For a given prime p, there are not very many elements with small order;
almost all elements have large order. However, finding an element of
small order is easy IF one has the factorization of...
|
|
Forum: Math
2007-11-13, 12:48
|
|
Replies: 7
Views: 1,171
|
|
Forum: Math
2007-11-13, 06:44
|
|
Replies: 7
Views: 1,171
efficient generation of highly non-primitive roots
Is there a way to systematically generate highly non-primitive roots. But that I mean keeping the base the same and modding it with a generated prime such that the resulting order of the base has a...
|
