Ask Your Question

Generate a random integer with some condition

asked 2024-06-20 00:44:22 +0200

hamouda gravatar image

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2024-06-20 01:42:15 +0200

Max Alekseyev gravatar image

$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
edit flag offensive delete link 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. ??

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

What specific condition?

Max Alekseyev gravatar imageMax Alekseyev ( 2024-06-20 02:06:29 +0200 )edit

A general condition according to my choice

hamouda gravatar imagehamouda ( 2024-06-20 02:08:55 +0200 )edit

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

Max Alekseyev gravatar imageMax Alekseyev ( 2024-06-20 02:11:43 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2024-06-20 00:44:22 +0200

Seen: 100 times

Last updated: Jun 20