|
For DSA verify what methods in you library would be called to calculate v?
Calculate w=s^-1 mod q
Calculate u1=H(m) * w mod q
Calculate u2=r * w mod q
Calculate v=((g^u1 * y^u2) mod p) mod q
The signature is valid if v=r
|
|
|
|
|
Hello,
For w = s^-1 mod q use ModularInverse(BigInteger a, BigInteger n).
For modular multiplication simply use the standard operator overloading within BigInteger (* for multiplication, % for modulo).
For v = ((g^u1 * y^u2) mod p) mod q = ((g^u1 mod p * y^u2 mod p) mod q, use ModularExponentiation(BigInteger a, BigInteger exponent, BigInteger n) and then the multiplication (*) and modulo (%) operator.
Best regards,
Mihnea
modified 20-Aug-18 21:01pm.
|
|
|
|
|
how to convert the biginteger to double or int after doing the calculations?
|
|
|
|
|
Hi curvers!
BigInteger aBigInteger;
string aBigIntegerAsBase10String = aBigInteger.ToString();
int aBigIntegerAsInt = int.Parse(aBigIntegerAsBase10String);
double aBigIntegerAsDouble = double.Parse(aBigIntegerAsBase10String);
Cheers,
Mihnea
modified 20-Aug-18 21:01pm.
|
|
|
|
|
why the implementation of encryption with rsa cannot be compressed with huffman compression ? .. please help me ..
|
|
|
|
|
Hi Muhammad,
At the time I implemented this I didn't think encrypted message compression was necessary. You can, of course, compress the resulting RSA-encrypted file (a binary file) using any compression algorithm of choice (for example, .NET offers GZip compression - GZipStream class).
Best regards,
Mihnea
modified 20-Aug-18 21:01pm.
|
|
|
|
|
very good articles
thanks
|
|
|
|
|
Hello everybody!
I have been looking into Smalltalk implementations lately and have found their numeric types quite impressive. On the one hand, they are full-fledged objects (no auto-boxing and unboxing syntactic sugar), on the other they get automatically extended and reduced to the appropriate types, depending on the messages sent to them.
| x y |
x := 20 factorial.
x class.
y := (x / (19 factorial)).
y class
In this case, x class is LargePositiveInteger, while y class is SmallInteger. Overall, Smalltalk features the best native numerics support I have seen in terms of natural use, except for the standard mathematical precedence of operators not being taken into account (they are messages sent to objects, nothing more).
All the best,
Mihneamodified on Tuesday, February 23, 2010 1:53 PM
modified 20-Aug-18 21:01pm.
|
|
|
|
|
Ah, I do like that approach. I think Python does something similar.
|
|
|
|
|
FYI
BigInteger support will be available in .NET framework 4
System.Numerics.BigInteger is an arbitrary-precision integer data type. BigInteger supports all the standard integer operations, including bit manipulation. It can be used from any .NET language, and some of the new .NET languages—such as F# and IronPython—have support built-in to the language. We partnered with the Microsoft Solver Foundation team to deliver this in .NET 4.
Regards,
Seb
|
|
|
|
|
Indeed, but can the assembly containing System.Numerics.BigInteger be referenced and distributed with a .NET 2.0 application? It will be a long while until everyone migrates to .NET 4.0 (the company I work for still uses .NET 2.0 due to customer requirements).
|
|
|
|
|
Hello to both of you!
Indeed, .NET 4.0 Beta 2 exposes a BigInteger type, but, obviously, it is not backwards compatible with .NET 2.0. A .NET 4 project can import any .NET 2.0, .NET 3.0 and .NET 3.5 assemblies, but not the other way around. By the way, Visual C# 2010 Express Edition, featuring .NET 4 Beta 2, is available for free download.
.NET 2.0 is still, by far, the most used .NET version around, as WPF, WCF, LINQ and ADO.NET Entity Framework, although used in projects, still have to gain mainstream acceptance.
Best regards,
Mihnea
modified 20-Aug-18 21:01pm.
|
|
|
|
|
That is true, however the implementation in System.Numerics is missing some essential methods like IsPrime, ModularExponentiation, ModularInverse, IntegerSqrt, and without the source code, we don't have the option to add them.
Is there a plan to add these in next update of .NET 4.0 ?
|
|
|
|
|
.NET 4.0 supports adding extension methods even to sealed classes, that are client-visible using IntelliSense.
Since all of the methods mentioned above can be implemented on top of the four elementary arithmetic operations, one does not need details pertaining to implementation internals. You can even use my own implementation of these operations in your BigInteger extension class, with few modifications, if necessary.
If you are really curious about the MS BigInteger implementation, download the Reflector tool. MS did not obfuscate the code, so it's easy to see it all in clear.
All the very best,
Mihnea
modified 20-Aug-18 21:01pm.
|
|
|
|
|
Hi,
I of course know about extension methods, however I doubt that without the ability to manipulate with the private members the operations will have any reasonable performance. Of course, I might be wrong, so I an going to try it  . As for the reflector trick, I already tried that and unfortunately the disassembled BigInteger type in System.Numerics.dll shows very little implementation details (I am not sure if that is caused by code obfuscator).
|
|
|
|
|
1) BigInteger.equals does not guard against null argument o
2) Don't need to overload operators for long / BigInteger permutations if you create a implicit conversion operator for long to BigInteger (various implicit and explicit conversion operators would be nice in general)
3) It's a shame the length of the BigInteger has to be fixed, and also that digits[] has to be allocated with MaxSize even for smaller BigIntegers.
4) Why not make BigInteger a struct instead of a class?
5) I too am interested in this subject and implemented a version in base-10 with a LinkedList: BigInt[^]. Like you, I found the division algorithm to the most challenging.
Good stuff, I bet this works well for your purposes, but I think the interface could be spruced up a bit to make it appealing to the general public.
Stephen Swensen
|
|
|
|
|
Thanks Stephen for the interest shown in this library, as well as for the constructive criticism!
1) BigInteger does not explicitly guard against it, but it will trigger a NullReferenceException as the inherited behavior from Object. Otherwise one would need to wrap the NullReferenceException into a BigIntegerException for every method receiving a BigInteger parameter, which will be superfluous, while achieving nothing extra.
2) Thanks for the tips, I'll definitely replace the unnecessary operator overloads with a long-to-BigInteger implicit conversion operator. This will definitely clean up the redundancies and, thus, improve code readability and maintainability. As to explicit conversion operators, I am rather skeptical that a lossy convertion method that throws an exception most of the time is a good OOP practice. I'll rather have the client programmer parse the ToString() output of a BigInteger, if one needs such a conversion.
3) Allocation of dynamic data in garbage collected languages is very fast, compared to languages with manual memory management (a malloc call), since there is always a GC pointer to the first byte of free memory and the memory is periodically defragmented, so memory allocations are virtually equal to O(1) in complexity.
Primitive operations are only performed on the occupied portion of the memory, making this solution faster than an apparently memory-saving periodic deallocation / reallocation of storage which uses extra CPU cycles.
4) Related to point 3. Heap allocation is very fast on managed platforms, one does not need the stack allocation option from C/C++. Stack overcrowding is a thing of the past, except for low-level programming.
5) Using a sequential data structure, requiring O(n) time to get to the specified index, severely limits the speed of indexed accesses, which would only need constant time (O(1)) in an array-based solution (see all of the basic algorithms). Memory conservation always comes second to CPU clock cycle reduction, especially in this case, where the memory footprint may actually be higher, since a linked list element's size is the size of the contained element + the size of a pointer (64 bit on 64-bit OS's).
Processor cycles used for an application are never few enough, but, more often than not, memory is abundant. Embedded devices with particular CPU / memory configurations are, of course, a completely different story.
All the very best,
Mihnea
modified 20-Aug-18 21:01pm.
|
|
|
|
|
I'm glad my comments could be of some value to you. As a follow up, for #1 I don't suggest throwing an exception if o is null (perhaps I misused "guard"), rather, return false since this will never equal null. Indeed, relating to #4, I'm not concerned about the cost of allocation, rather, BigInteger is logically a ValueType the same way all the built-in .NET numeric types are, and by making it a struct you wouldn't have to worry about null BigInteger arguments whatsoever. #5: in all my algorithms I never used indexed access, that being said, I think the best solution would use an array dynamically sized based on the maximum size possibly required by a given operation (that's the approach taken by Java's BigInteger implementation: http://www.docjar.com/html/api/java/math/BigInteger.java.html[^]). I appreciate your argument in favor of saving CPU cycles over conserving memory, but it really all depends: the C# BigInteger Class[^] implementation similarly uses a fixed length array, and found myself running into out of memory exceptions with memorization based algorithms which is what lead me to develop my own implementation which isn't nearly as fast but lets me work safely with many very large numbers.
Sorry for the kind of big sloppy paragraph, but it's time to go home now!
Stephen
|
|
|
|
|
Thanks again for the reply featuring valuable intel, Stephen!
Regarding stack allocation, putting the BigInteger on the stack doesn't tie it to the stack completely. The array itself has to be allocated unsafely using stackalloc. This eliminates the possible usage of List for dynamic growth and entails the creation of a custom-made dynamic array allocator. Then, the whole object will be a basic data holder and behave like a primitive type. However, in the context of possible heavy recursive algorithms on large date sets, I'll rather keep the stack clean just to be safe.
Dynamic arrays (say, List<t>) could be an improvement if one manages to define the adequate cut-points for reallocation (powers of two, probably, like in the case of STL containers in C++). Anyway, dynamic heap allocation and deallocation are very fast in managed languages. This is where C++ apps without a custom-designed memory allocator have been performance-wise beaten when dealing with a high amount of small short-lived objects.
In general, optimizations rely on some tweaking of the variables and improving the algorithms in the project, not on using a higher order complexity algorithm. There has to be an overwhelming justification to use a linear algorithm over a constant time one and increase each elements required storage by a machine word (LinkedList vs. List (or array)). LinkedList's are adequate only in the case of frequent insertions and deletions from within the structure (say, a sparse BigInteger or a polynomial over BigInteger's).
Best regards,
Mihneamodified on Monday, February 22, 2010 6:42 PM
modified 20-Aug-18 21:01pm.
|
|
|
|
|
<a href="http://www.codeproject.com/KB/cs/biginteger.aspx">C# BigInteger Class</a>[<a href="http://www.codeproject.com/KB/cs/biginteger.aspx" target="_blank" title="New Window">^</a>]
|
|
|
|
|
Yes, I've seen it. It's a nice implementation.
modified 20-Aug-18 21:01pm.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
