Tag Info

Hot answers tagged

9

As a computer science student who took a graduate course (albeit an introductory one) in cryptography last semester, I found myself pulling from my knowledge of number theory immensely more than I did from my knowledge of computer science. The field today is a highly mathematical one, with current state-of-the-art systems reliant on number theoretical ...


5

In a sense, both of your ideas (computer science and pure mathematics) are both correct for what might be suitable for cryptography. RSA encryption is based on abstract algebra concepts, and also the computer science belief that factoring integers is hard unless on a quantum computer. You can read about RSA online, there's plenty of references and if you ...


3

Using this cryptogram solver, I get the solution "Freddie Starr ate my hamster".


3

Generating large primes is not difficult. For example, using PARI/GP, randomprime([10^99, 10^100]) generates a random 100-digit prime in about 2 milliseconds. An implementation which need not follow a strict uniform distribution could be much faster. For full cryptographic strength, see FIPS 186-4. The hard problem is factoring large semiprimes, not ...


2

This answer is for the concrete values of $p,a,b$ given in the question; it relies on $p\equiv 7\pmod{9}$, $a=0$, $\left(\frac{b}{p}\right)=-1$. The key property is that $p-1$ is divisible by $3$, but not by $3^2$. Instead $p+2$ is divisible by $3^2$. This allows us to follow an approach for cuberoots analogous to the one used for finding squareroots when ...


2

Much of cryptography today works on grounds of abstract algebra (and number theory). Clearly to show that some encryption technique has a corresponding decryption one requires proof, that is math. But that is just a small part of cryptography. The recent most talked about problems with cryptographic systems have been programming errors, disregard of the ...


1

This is an odd question, you are increasing the amount of bits required to encode the SSN. A decimal is encodable is roughly 3.32 bits, a hex value is 4 bits, so you could uniquely describe every single US SSN possible in that value, with room to spare, much less your 80,000. This means there should be no collisions, for reference. You could encode every SSN ...


1

Here's what's known to the best of my knowledge. If one multiplies two nonzero sequences of periods $T_i$, $i=1,2$ over the same field, one obtains a sequence with period in the interval $$\left[\frac{T_1 T_2}{gcd(T_1,T_2)},T_1 T_2\right].$$ If two $m-$sequences over $GF(q)$ whose minimal polynomials have relatively prime degrees $d_i$ are multiplied then ...


1

As I outlined in the same question you crossposted, this is essentially a factorization problem; you're given a polynomial over $GF(2)$, and you want to know the pairs of possible products that make up that polynomial. This can be reduced to factoring the polynomial into the multiset of prime factors (in the case you listed, the factorization is $73af = 83 ...


1

This is a somewhat stupid case for Miller-Rabin because you should assume that n is not a square. Anyway. Let $n=25$ and $a=2$ the smallest possible candidate, then $n-1=d\times 2^s = 3\times 2^3.$ Now compute $$x_0 \equiv a^d \equiv 2^3 \equiv 8 \pmod{25}$$ $$x_1 \equiv x_0^2 \equiv 14 \pmod{25}$$ $$x_2 \equiv x_1^2 \equiv 21\pmod{25}$$ Thus $a^d\not ...


1

If it is a finite graph, the answer is yes, because for fixed $n$ there is only a finite number of paths of length $n$ in the graph. For example, you can enumerate all $n$-tuples of distinct vertices in the graph, check whether they form a path, compute the hash value of that path if they do, and check if that hash occurs in your list of hashes.


1

One way of attacking this is to note that the requirements on $a$ is that, for all prime factors $p$ of $n$: $$a^{n-1} \equiv 1 \pmod{p}$$ If we go through the prime factors of $n$ (5, 7), we find that the above is equivalent to: $$a \equiv \{1, 4\} \pmod{5}$$ $$a \equiv \{1, 6\} \pmod{7}$$ By the Chinese remainder theorem, that implies that there are ...


1

Note that because $g^q = 1$ (the neutral element), we have in general, $$g^{ab} = g^{ab} 1 = g^{ab} g^{qab} = g^{ab (q+1)} = g^{2ab \frac {q+1} 2} = \big( g^{2ab} \big) ^{\frac {q+1} 2} = \big( g^{(a+b)^2 -a^2 -b^2} \big) ^{\frac {q+1} 2} =\big( A(g^{a+b}) A(g^a)^{-1} A(g^b)^{-1} \big) ^{\frac {q+1} 2} ,$$ the last expression being able to be implemented ...



Only top voted, non community-wiki answers of a minimum length are eligible