英文:
Reverse engineer a number for Math.random() in Java, based on a random string
问题
因此，我在处理一个小问题时有一个问题。
通过任意长度的Java程序生成的随机字符串，例如jdefreq。
字符串中的每个字符都是使用以下方式生成的，
final String[] dict = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r",
"s", "t", "u", "v", "w", "x", "y", "z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", ",", ".", "?" };
final int dictIndex = (int)Math.floor(Math.random() * dict.length);
我有一种复制Math.random()的方法，但我需要得到确切的第一个数字，该数字在序列中起始使用。
我目前尝试的方法是获取第一个字符，然后循环使用Math.random()，直到获得一个可以产生与该第一个字符相同索引的数字，但这还不够，因为我只能产生一个类似的数字，而不是完全相同的数字。
所以我来到这里，各位程序员！
是否有人知道我该如何做才能实现这一点？
非常期待听取大家对这个问题的建议和他们的观点！
谢谢，祝你有美好的一天！
英文:
So I have a question on a little problem I am working on.
Given a random string generated by a java program of any length e.g. jdefreq.
Each character within the string is generated using,
final String[] dict = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r",
"s", "t", "u", "v", "w", "x", "y", "z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", ",", ".", "?" };
final int dictIndex = (int)Math.floor(Math.random() * dict.length);
I have a way to replicate Math.random() but I need the exact first number, that is used starting off within the sequence.
The way I have been trying to go about it, right now is take the first character, and loop with Math.random() until I get a number that can reproduce the same index of that first character, but that's not good enough since I only produce a similar number, but not the exact same one.
So I have came here fellow programmers !
Does anybody have any idea how / what I can do to be able to pull this off ?
Really excited to hear people's advice / their POV on the problem !
Thanks and have an awesome day !
答案1
得分: 2
为了深入阐述我的评论：只有 248 种不同的序列可以由 Math.random 生成。这还是相当多的，但并不多到你不能在可思量的时间内尝试所有这些序列。设置如下：
for (long seed = 0; seed < (1L << 48); seed++) {
Random r = new Random(seed);
if (generateString(r).equals(desiredString)) return seed;
}
其中 generateString(r) 的生成方式相同，只是使用 r.nextDouble() 替代了 Math.random()。
另一种方法是将相关设置编码为满足模理论（SMT），然后将求解器应用于它。由于 Java 的伪随机数生成器是线性同余生成器，不使用除法，所以这部分并不太难。一开始，人们可能会想象我们必须为 Random.nextDouble() 实现浮点算术，但我们可以直接根据 nextDouble() 生成的 53 位整数来推理范围。总的来说，虽然这很繁琐，但相对而言相当直接，因为复杂的算法逻辑被封装在求解器中。
英文:
To expand on my comment: there are only 2<sup>48</sup> distinct sequences that Math.random can produce. That's quite a lot, but not so many that you can't try all of them in a thinkable amount of time. The setup looks like
for (long seed = 0; seed < (1L << 48); seed++) {
Random r = new Random(seed);
if (generateString(r).equals(desiredString)) return seed;
}
where generateString(r) generates strings the same way except using r.nextDouble() instead of Math.random().
Another approach would be to code the relevant setup as a satisfiability modulo theory and then throw a solver at it. Since Java's pseudorandom number generator is a linear congruential generator that doesn't use division, that part isn't too hard. Naively one might imagine that we have to implement floating-point arithmetic for Random.nextDouble(), but we can reason directly about ranges with respect to the 53-bit integer that nextDouble() generates. All in all, this is tedious but relatively straightforward because the complicated algorithm logic is encapsulated in the solver.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论