# Factorizing BigInt, partially if necessary
**URL:** https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524
**Category:** General Usage
**Created:** [November 12, 2024, 7:32am UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524 "2024-11-12T07:32:06Z")
**Posts on this page:** 9
**Page:** 1
### Author:  [@phma](https://discourse.julialang.org/u/phma)
#### Post date: [November 12, 2024, 7:32am UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/1 "2024-11-12T07:32:06Z")
I’d like to write a function to generate big primes and semiprimes suitable for cryptography. It’s important to try to factor p-1; the primes should at least be in [A073024](https://oeis.org/A073024). But I could encounter a number which can’t be completely factored in a reasonable time, in which case I should discard it. What package can I use to test primality of and try to factor such big numbers?
---
### Author:  [@abraemer](https://discourse.julialang.org/u/abraemer)
#### Post date: [November 12, 2024, 11:46am UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/2 "2024-11-12T11:46:08Z")
I think using Primes.jl could be a starting point but I have no personal experience with it and certainly not with cryptographic primes so I can’t tell whether it will be sufficient for you.
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [November 12, 2024, 12:56pm UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/3 "2024-11-12T12:56:00Z")
> [@phma](#):
>
> What package can I use to test primality of and try to factor such big numbers?
For cryptographic applications, normally one uses probabilistic primality testing, not factoring. [`Primes.isprime(p-1)`](https://juliamath.github.io/Primes.jl/v0.1/api.html#Base.isprime) does this — you can easily make the probability of a false positive arbitrarily low (it is \approx 1/10^{15} with the default arguments).
---
### Author:  [@phma](https://discourse.julialang.org/u/phma)
#### Post date: [November 12, 2024, 3:41pm UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/4 "2024-11-12T15:41:50Z")
[`Primes.isprime(p-1)`](https://juliamath.github.io/Primes.jl/v0.1/api.html#Base.isprime) will immediately fail because p-1 is even. Once I know that p is prime, I need to find out if p-1 has a prime factor greater than p^(2/3).
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [November 12, 2024, 4:01pm UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/5 "2024-11-12T16:01:13Z")
Sorry, I was thinking of `isprime(p)`, for an RSA-like algorithm where you generate two large primes and multiply them.
Not sure what they do in cryptography to ensure that p-1 has large prime factors, but I’m guessing it’s probabalistic?
---
### Author:  [@mstewart](https://discourse.julialang.org/u/mstewart)
#### Post date: [November 12, 2024, 4:40pm UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/6 "2024-11-12T16:40:27Z")
This is totally not my field at all, but about 15 years ago I did some reading on this sort of thing while teaching an undergraduate course. I think generating the prime p and checking p-1 is backward. You want to focus on making sure p-1 has the desired large prime factor first and then check the primality of p second. So you can generate a prime q that is suitably large to be an acceptable prime factor of p-1 and then set p = jq + 1 for different values of j that make p suitably large. You can test each candidate p for primality and then, once you have found that p is prime, p-1 will have q as a prime factor.
Edit: Thinking a little more, you should use just even values of j, because otherwise p-1 will be odd and p will be even, which is obviously not what you want.
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [November 12, 2024, 5:24pm UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/7 "2024-11-12T17:24:15Z")
note that modern guidance iiuc doesn’t require testing for “safe primes” since approximately 100% of 2048 bit primes are safe
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [November 12, 2024, 8:03pm UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/8 "2024-11-12T20:03:00Z")
> [@stevengj](#):
>
> Not sure what they do in cryptography to ensure that p-1p−1p-1 has large prime factors, but I’m guessing it’s probabalistic?
They have typically discarded cryptography based on large primes. They are being replaced by newer schemes based on code theory and lattice theory etc.
[https://csrc.nist.gov/publications/fips](https://csrc.nist.gov/publications/fips)
---
### Author:  [@phma](https://discourse.julialang.org/u/phma)
#### Post date: [November 13, 2024, 5:01am UTC](https://discourse.julialang.org/t/factorizing-bigint-partially-if-necessary/122524/9 "2024-11-13T05:01:32Z")
The purpose of p-1 having a factor greater than p^(2/3) is to prevent factorization by noisy quantum computers (all quantum computers so far are noisy), as mentioned on the OEIS page. I think elliptic curve factorization would be a good method to try. Has anyone implemented elliptic curve factorization in Julia?
Except for 5 and 7, all safe primes are noisy-quantum-proof primes. The fraction of primes which are noisy-quantum proof is known to be positive; the fraction of primes which are safe is not.