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.
$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
@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. ??
It depends on the type of condition. Any modular condition can be treated similarly to what's done in my answer.
Asked: 2024-06-20 00:44:22 +0100
Seen: 167 times
Last updated: Jun 20
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
