I have a feeling that making it threadsafe under any quantity of threads and still perform is likely not feasible, but if I could; or if making a nonthreadsafe variant was possible:
Creating a mathematical proof that somehow is “simple and probably correct” enough, would be an impossible task even for a PhD mathematician. How did someone prove the current implementation was cryptographically sound? Did they run massive simulations which ran the gamut of the uint32_t range which demanded tight tolerances over varying length runs? How was rc4 cipher proven bad for pseudorandom numbers? I’d be willing to bet it wasn’t from a mathematical proof; it was from bad data. I’m guessing that large upperbounds approaching 2**32 don’t feed very soundly in the current implementation using a modulus; although I suspect that there isn’t much of a call for such things, I’m pretty sure I saw a 3,000,000,000 upperbound in the src partition tonight. On Sun, May 15, 2022 at 3:15 AM Otto Moerbeek <o...@drijf.net> wrote: > On Sun, May 15, 2022 at 01:12:28AM -0500, Luke Small wrote: > > > This is version 1, which I was pretty sure was secure. > > > > I revamped it with a few features and implanted the binary search for > 'bit' > > > > in most cases, which aren't intentionally worst-case, it's pretty darned > > fast! > > > > This is a sample run of my program with your piece of code included: > > > > > > 1 99319 100239 > > 2 100353 99584 > > 3 100032 99879 > > 4 99704 100229 > > 5 99530 99796 > > 6 99617 100355 > > 7 100490 100319 > > 8 99793 100114 > > 9 100426 99744 > > 10 100315 100558 > > 11 99279 99766 > > 12 99572 99750 > > 13 99955 100017 > > 14 100413 100005 > > 15 100190 100052 > > 16 101071 100195 > > 17 100322 100224 > > 18 99637 99540 > > 19 100323 99251 > > 20 99841 100177 > > 21 99948 99504 > > 22 100065 100031 > > 23 100026 99827 > > 24 99836 99818 > > 25 100245 99822 > > 26 100088 99678 > > 27 99957 99993 > > 28 100065 99961 > > 29 100701 100679 > > 30 99756 99587 > > 31 100220 100076 > > 32 100067 100005 > > 33 99547 99984 > > 34 100124 100031 > > 35 99547 100661 > > 36 99801 99963 > > 37 100189 100230 > > 38 99878 99579 > > 39 99864 99442 > > 40 99683 100004 > > 41 99907 100094 > > 42 100291 99817 > > 43 99908 99984 > > 44 100044 100606 > > 45 100065 100120 > > 46 99358 100141 > > 47 100152 100442 > > 48 100000 100279 > > 49 100486 99848 > > Sadly a sample run cannot be used to proof your implementation is > correct. It can only be used to show it is not correct, like Philip > did. To show your implementation produces uniform results in all > cases, you need to provide a solid argumentation that is easy to > follow. So far you failed to do that and I do not see it coming, given > the complexituy of your implementation. The current implementation > has a straightforward argumentation as it uses relatively simple > mathematical properties of modulo arithmetic. > > It is also clear your code (as it uses statics) is not thread safe. > > So to answer you original question clearly: no, we will not accept this. > > -Otto > -- -Luke
