# Generate a random integer with some condition

I want to generate a random integer of bitsize $n$ with some condition. For example, if we want to generate an integer $e$ of 71 bits satisfying $3e= 1 \bmod 5$, in which the generation is fast to some extent. How to do this in sage.

edit retag close merge delete

Sort by ยป oldest newest most voted

$3e\equiv 1\pmod5$ means that $e=5k+2$ for some $k$. Then $e$ having $n=71$ bits means $e\in[2^{n-1},2^n-1]$, which translates into $k\in \big[\lceil (2^{n-1}-2)/5\rceil, \lfloor (2^n-3)/5\rfloor\big]$. Hence, it's enough to generate such a random integer $k$, and then compute $e$ out of it:

n = 71
L = ceil((2^(n-1)-2)/5)
U = (2^n-3)//5
import random
e = random.randint(L,U)*5 + 2

more

@Max Alekseyev, It is a good idea for this example. If it is possible, is there a general way to generate an integer of bitsize n, with a specific condition. ??

( 2024-06-20 01:56:58 +0200 )edit

What specific condition?

( 2024-06-20 02:06:29 +0200 )edit

A general condition according to my choice

( 2024-06-20 02:08:55 +0200 )edit
1

It depends on the type of condition. Any modular condition can be treated similarly to what's done in my answer.

( 2024-06-20 02:11:43 +0200 )edit