# Questions tagged [prime-numbers]

A prime number is an integer greater than 1 with no divisors other than itself and 1. Primes and prime products play an important role in public key cryptography.

291 questions
Filter by
Sorted by
Tagged with
546 views

### Timelock puzzle improvment

I came across this question with this answer about a cryptographic timelock-puzzle that needs approximately 30 years to be solved. There is also an explanation with source code for that puzzle ...
1k views

### Solving congruences using PARI

I'm having trouble finding info in the docs about how to solve a system of congruences. The closest I can find is 'matsolvemod' in here: http://pari.math.u-bordeaux.fr/dochtml/html.stable/Vectors,...
96 views

### Prime Factorization in RSA always leads to the product of two primes?

Lets prime factorize $30$: $$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$ We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two ...
424 views

### Finding the prime factors of $n'$ given the previous $n$ and its prime factors $p$ and $q$

Say I have a very large number $n$ = $pq$ where $p$ and $q$ are prime. A new number $n'$ is generated by increasing these prime factors. How can I find this new number's prime factors?
43 views

69 views

### Trial division + Miller-Rabin complexity

I was reading a paper that shows time complexity of Trial division + Miller-rabin test for creating prime number. T = N(T_rnd + T_td + T_mr) T_rnd denotes time for making rnd number, T_td denotes ...
70 views

### If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors?

Suppose you are given an algorithm $A$ which takes $y \in \{0, 1, \ldots , N − 1\}$ as input, and outputs $x \in \{0,1,\ldots,N − 1\}$ such that $x^2 \equiv y \pmod{N}$. Design an efficient, ...
18 views

### In practice, do large prime generators account for difference in gaps between primes? [duplicate]

It is my understanding that a method for creating large primes is to: pick a random large number, check the number against trial division of a set of smaller prime numbers, check with something like ...
81 views

68 views

### Finding two primes that satisfy the conditions

I want to implement partially blind signature, and I looked at Zheng Gong's scheme. (Title: Efficient Partially Blind Signature Scheme with Provable Security) In the scheme, there is a initialization ...
463 views

### What is the danger if a non-prime is chosen for RSA? [duplicate]

I was reading this question about generating primes for RSA keys. The answers point out that most implementations of of the algorithm use probabilistic prime-ness checking algorithms. The answer by @...
269 views

### Property of Multiplicative group of integers mod n

While practising on paper I've realized of a property of multiplicative group of integers mod $n$. First, let's define $G$ being $p$ a prime and $g$ a primitive root mod n or a generator of a ...
632 views

296 views

### RSA and Prime numbers distribution law [duplicate]

I have read a few articles and watched some Youtube videos explaining the algorithm of RSA. It seems that RSA is mainly based on a mathematical trick (Prime Factorization). I am wondering though what'...
139 views

### are all elements of ZpxZp in ECC definite over Zp

are all elements of ZpxZp in ECC (elliptic curve) definite over Zp ? otherwise: assume G a base point of ECC and n the order of G. why n is equal or nother to p*p ? (p a prime number). (Think to a ...
{"ft_lang_label":"__label__en","ft_lang_prob":0.88977754,"math_prob":0.98086196,"size":11835,"snap":"2020-45-2020-50","text_gpt3_token_len":3133,"char_repetition_ratio":0.15501648,"word_repetition_ratio":0.012757606,"special_character_ratio":0.26370934,"punctuation_ratio":0.11509591,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99703497,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-30T23:09:06Z\",\"WARC-Record-ID\":\"<urn:uuid:0902f690-69ea-4e51-bdb2-a3a819be8e23>\",\"Content-Length\":\"226448\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fdfe65b8-c50b-4f57-a7b8-03c3bc7cbee3>\",\"WARC-Concurrent-To\":\"<urn:uuid:9e99052f-3832-4077-85ad-b1c3429a25df>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://crypto.stackexchange.com/questions/tagged/prime-numbers?tab=votes&page=6\",\"WARC-Payload-Digest\":\"sha1:AEIWURRYZAGZEBAUECIEUYOOM4NS7AEN\",\"WARC-Block-Digest\":\"sha1:D2ZIK53HLO3LJPEYOASCGKQY5MFFTQTX\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-45/CC-MAIN-2020-45_segments_1603107911792.65_warc_CC-MAIN-20201030212708-20201031002708-00179.warc.gz\"}"}