Category: math

Supply Chain Logistics and SAP TM

· Leave a comment ·

SAP Transportation Management or SAP TM is a module used for Supply Chain Optimization.

SAP TM has four different optimizer engines –

VSR Optimizer: Plan Shipments in the best possible way on available Vehicles via available routes. TVSR (Vehicle scheduling and routing), TVSS, TVRG Applications come under this.

Load Optimizer: Arrange pallets or packages on the vehicle considering rules like Stackability, etc. (TVSO Application)

Carrier Selection: Rank carriers[1] for each shipment considering costs, Business Shares, Allocations. (TSPS Application)

Strategic Freight Management: Rank bids by carriers for long-term contracts based on Cost, Capacity & Risk. (TSFM Application)

The need for Transportation Management as a service is justified by several use cases.

Many recent announcements from leading car manufacturers and other companies whose business models are susceptible to disruption are adopting TaaS platforms (through in-house development efforts, partnerships, or acquisitions) to provide services:

The role of APIs in modernizing supply chain systems from legacy EDI based designs – https://www.coupa.com/blog/supply-chain/tech-forward-apis-emerging-player-supply-chain

A comparison of API vs EDI systems – https://arcb.com/blog/edi-vs-api-which-is-right-for-my-business

Some definitions from Wikipedia to clarify concepts-

Logistics is generally the detailed organization and implementation of a complex operation. In a general business sense, logistics is the management of the flow of things between the point of origin and the point of consumption to meet the requirements of customers or corporations.

The resources managed in logistics may include tangible goods such as materials, equipment, and supplies, as well as food and other consumable items.

Logistics management is the part of supply chain management and supply chain engineering that plans, implements, and controls the efficient, effective forward, and reverse flow and storage of goods, services, and related information between the point of origin and point of consumption to meet customer’s requirements. The complexity of logistics can be modeled, analyzed, visualized, and optimized by dedicated simulation software.

The minimization of the use of resources is a common motivation in all logistics fields.

A supply chain is the connected network of individuals, organizations, resources, activities, and technologies involved in the manufacture and sale of a product or service.

How can we be better prepared for a future crisis relative to supply chains?

Private companies have playbooks for supply chain disruptions in their network. In supply chain management, it is crucial to diversify your source of supplies so that when one supplier is impacted, you can turn to the other.

Git Merge. You are in the middle of a merge. Cannot Amend.

· 3 Comments ·

Let’s say I made changes to branch “abc”, committed and pushed them.  This fired a build and a code-review after which the code is ready to be merged. But before these changes are merged, another party merged changes from a branch “xyz” into “abc”.

How do I replay my changes on top of changes from “xyz” in “abc” ? Here’s a seemingly obvious command to try:

$ git pull origin abc // tldr don't do this. try git pull --rebase
Auto-merging file1
CONFLICT (content): Merge conflict in file1
Automatic merge failed; fix conflicts and then commit the result.


At this point, I resolve the commits and attempt a git commit –amend. But this gives an error.

$ git commit --amend
fatal: You are in the middle of a merge -- cannot amend.
$ git rebase 
First, rewinding head to replay your work on top of it...
Applying: change name
Using index info to reconstruct a base tree...
M file1
Falling back to patching base and 3-way merge...
Auto-merging file1
CONFLICT (content):



The problem is the pull step, which implicitly does a fetch+merge and where the merge fails. (check git –help pull).

To recover from this situation, first squash the unnecessary merge and then do a rebase.

$ git reset --merge 
$ git rebase
First, rewinding head to replay your work on top of it..



This shows a list of conflicting files. Find the conflicting files and edit them to resolve conflicts.














$ git rebase --continue

file: needs merge

You must edit all merge conflicts and then mark them as resolved using git add



  
$ git add file1 file2



$ git rebase --continue

Applying: change name


  
$ git commit --amend




$ git push origin HEAD:refs/for/abc

Here’s the git rebase doc for reference. The rebase command is composed of multiple cherry-pick commands. Cherry-pick is a change-parent operation and changes commit-id = hash(parent-commit-id + changes). Here it re-chains my commit on top of a different commit than the one I started with. The commit –amend would not have changed the commit-id, and so it would not change the parent, so it fails.

Git merge is an operation to merge two different branches. It is the opposite of git branch, which creates a branch. In the above example we are applying our local changes to the same branch, which has undergone some changes since our last fetch.

Another error sometimes seen during a cherry-pick is the “fatal: You are in the middle of a cherry-pick — cannot amend”.  This happens on a “git commit –amend”  and here it expects you to do a plain “git commit” to first complete the cherry-pick operation.

A git commit references the current set of changes and the parent commit. A git merge references two parent commits. A git merge may involve a new commit if the two parents have diverged and conflicts need to be resolved.

Some idempotent (safe) and useful git commands.

$ git reflog [--date=iso]  # show history of local commits to index
$ git show  # or git show commit-hash, git show HEAD^^
$ git diff [ --word-diff | --color-diff ]
$ git status # shows files staged for commit (added via git add to the index). different from git diff
$ git branch [-a]
$ git tag -l   # list all tags 
$ git describe # most recent tag reachable from current commit
$ git config --list
$ git remote -v # git remote is a repo that contains the same proj 


$ git fetch --dry-run

$ git log --decorate --graph --abbrev-commit --date=relative --author=username

$ git log --decorate --pretty="format:%C(yellow)%h%C(green)%d%Creset %s -> %C(green)%an%C(blue), %C(red)%ar%Creset"

$ git log -g --abrev-commit --pretty=online 'HEAD@{now}'

$ git grep login -- "*yml"

$ tig    # use d, t, g to change views; use / to search

$ git fsck [--unreachable]

$ git verify-pack -v .git/objects/pack/pack-*.idx | grep -v chain | sort -k3nr | head  # list of largest files

$ git cat-file -p <hash> # view object - tree/commit/blob

$ git clean -xdn

Difference between ‘origin’ and ‘upstream’ terms is explained here. An interactive git cheat sheet is here. There is only one origin, the one you cloned your repo from, there can be many remotes, which are copies of your project.

Update sequence: working_directory -> index -> commit -> remote

Some terms defined:

origin = main remote repository

master = default (master/main) branch on the remote repository

HEAD = current revision

git uses the SHA-1 cryptographic hash function for content-addressing individual files (blobs) and directories (trees)  as well as commits – which track changes to the entire tree. Since each tree is a SHA-1 hash over the SHA-1 hashes of the files it contains, the SHA-1 change of a child that is n-levels deep, propagates to the root of the tree.

The index used in ‘git add’ is under .git/index . It can be viewed with

$ git ls-files --stage --abbrev --full-name --debug

This does not store the file contents, just their paths. The content for a new commit is stored under .git/objects/<xy>/<z>    where xy is the first two digits of the hash and z is the rest of 40 char hash.  If you do a fresh checkout the .git/object is empty except for the .git/objects/pack directory which stores the entire commit history in compressed form in a .pack file and a .idx index file. An mmap is done on these files for fast searching.

 

I’d like to donate $5 to support this site.

Elliptic Curve Crypto – an algebraic introduction

· 2 Comments ·

A brief review of algebraic concepts leading to Elliptic Curve Cryptography (ECC):

Algebraic Group: A set G with a single binary operator (+) that maps any 2 elements of G to another element of G, where the operator supports closure, identity, inverse and associative properties. If the + operator is commutative, G is called an Abelian group or a Commutative group. [matrix multiplication and quaterion multiplication are not commutative; the symmetric group Sn for n>=3 is non abelian – because transformation order of permutations matters; S5 is not solvable https://youtu.be/ebc8EdBNA-E https://youtu.be/h6JBiYeBfC4 https://m.youtube.com/watch?v=oM1LD80E7XU . I mention these because the notion of a group became useful and well-defined when non-Abelian groups such as S5 were encountered].  For ECC the groups involved are commutative or Abelian.

Algebraic Ring: A set R with a two binary operators (+) and (*) that map any 2 elements of G to another element of R. Every Ring is an Abelian group with respect to (+). If it is Abelian with respect to (*) then it is called a Commutative Ring. Note the absence of inverse or division requirement. [In Zp below, if p were not prime, then one would have a Ring instead of a Field because inverses would not always exist.]

Algebraic Field: A set F with a two binary operators (+) and (*) that map any 2 elements of F to another element of F; where (+) and (*) are both commutative; and where each element of F has a unique inverse with respect to (*), which is also in F. The set of Rationals form a Field, the set of Integers do not. The group properties are followed wrt (+) and (*) individually and the respective groups are the additive group and the multiplicative group.

Polynomial: A construct consisting of repeated applications of (+) and (*) on elements of a Field (which by definition of a Field returns another element of the Field ). The set of polynomials forms a Ring.

Closed Field: If the roots of every polynomial on a Field belong to the Field, it is a Closed Field. The set of Complex numbers form a Closed Field, the set of Reals do not. [A Field extension can be used to extend a non-Closed Field to a Closed Field].

Algebraic Finite Field: A Field with finite number of elements. It is not a Closed Field, but satisfies other properties of a Field, specifically that multiplication is invertible. The number of elements of the Finite Field is called its order. An example is the modulus field, obtained by modulo division by a prime number P. Note that exponentiation on a finite field generates a distribution of all the numbers in the sequence less than the order – for large values of an exponent it produces an highly irregular distribution. This makes the inverse operation of discrete logarithm a hard problem. The inverse of a specific element ‘a’ of a finite field of order n is a^(n-2), by Fermat’s little theorem.

Galois Field: Same as above, a finite Field. Finite fields have order pk, where p is a prime and k an integer>=1. All finite fields of a given order are isomorphic. In a field of order pk, adding p copies of any element always results in zero; that is, the characteristic of the field is p. If a finite field had a non-prime order with different factors that would imply that different elements of the field could be added to themselves a different number of times to give 0, but each element of a field must have the same characteristic . We met a  GF (28) in AES S-boxes.

Elliptic-Curve (over reals): A cubic equation, arises in calculation of arclength of an ellipse and naturally has a group property, where two elements on the curve map to a third element also on the curve. See here. The group property is used to define EC-addition (A+B), EC-doubling (A+A) and EC-scalar-multiplication (A+A+..A = kA). This is the group operation on Elliptic curves, a reasonable explanation of why it exists is here. These two operations are defined in more detail- http://www.coindesk.com/math-behind-bitcoin/ . Lets observe that they are distinct from, but dependent on the underlying field properties. The EC operations are maps on tuples or points.  In history of elliptic curves it notes that whereas ellipses are quadratic, elliptic curves are cubic or quartic, attributing the name linkage to Wallis. It also notes the tangent-secant method of  Diophantus in using two rational solutions of a cubic to find a third rational solution (later proved to be an Abelian Algebraic Group: points A and B on a curve map to a third point C, and one defines Group addition with A+B =-C, where the – is reflection around x-axis. https://crypto.stackexchange.com/questions/53974/when-adding-two-points-on-an-elliptic-curve-why-flip-over-the-x-axis makes the argument using symmetry of A,B,C; important thing is this ‘addition’ is not a linear operation). For a tangent, look at Frey Elliptic curves and Tate’s review with its discussion on isogenies.

Elliptic-Curve over a Field: The set of points (tuples) belonging to a field F that satisfy an elliptic curve equation (y*y = x*x*x+a*x+b) with the (+) and (*) defined according to the field.  Again the name elliptic curve arises because this equation comes up when calculating the arclength of the ellipse; the actual plot of this over different fields does not look like a curve let alone an ellipse. What’s interesting is that the Group property noted above is retained over different Fields. This lecture discusses how consideration of whether the area of a right triangle can be 1, over a field of rationals gave rise to elliptic curves – https://www.youtube.com/watch?v=6eZQu120A80.

Elliptic-Curve over a Finite Field: Tuples drawn from a Finite Field F, that satisfy the elliptic curve equation (y^2 = x^3+ax+b).

Elliptic-Curve Crypto: Built on the hardness of solving the discrete logarithm problem: Given an elliptic curve E defined over a finite field Fq of order(=size) n, a point P ∈ E(Fq ), and a point Q ∈ E(Fq ), find the integer k ∈ [0,n −1] such that Q = k P. The integer k is called the discrete logarithm of Q to the base P, denoted by k = logP Q. This is asking for an inverse operation. Introduction to ECC by Christof Paar – https://www.youtube.com/watch?v=vnpZXJL6QCQ .

In the Bitcoin implementation of ECDSA, the finite field is a prime modulus field Zp and the EC equation is y^2 (mod p) = x^3+7 (mod p).  Zp uses the prime modulus p=2^256 – 2^32 – 977 = 115792089237316195423570985008687907853269984665640564039457‌584007908834671663.  A 256 bit integer has (2^10)^25.6 or 3*25.6~77 digit numbers. So two 256 bit numbers are mapped to a third 256 bit number. Sounds good for encryption- but how is this inverted? It is not: one of the first numbers, the scalar multipler k, is the private key.  This 256-bit scalar private key is multiplied with a Generator Point G to arrive at a public key, with a 256bit x and y coordinates for a a 512-bit public key. From the kG, the private key k cannot be derived; the strength depends on this irreversibility. The “curve” on the finite field is highly discontinuous and an example is shown here. sepc256k1 is the name of the curve y^2=x^3+7, a list of other curves is here – https://neuromancer.sk/std/secg/

So how do we generate and verify a signature – an ECDSA ? This math is a layer on top of the preceding maps for generating keypairs. See https://en.m.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Correctness_of_the_algorithm for details and some implementation weaknesses. Openssl operations on EC based keypairs are described here – https://wiki.openssl.org/index.php/Command_Line_Elliptic_Curve_Operations. The size of the keys for EC are smaller than the size of RSA keys for equivalent security. Since the size of a signature is the same as the size of the key in bits, this means the EC signatures are shorter in size than RSA signatures. A 256 bit EC key takes 32bytes, compared to 512bytes for a (roughly) comparable 4096 bit RSA key.

An ECDSA signature of a message m is a pair of integers (r,s) where r does not depend on the message and s depends on the hash of the message, e, and on r.

The signature depends on a parameter k which should be random or deterministically generated via (say) RFC6979.

Other elliptic curves on finite fields, including on F(2^m) are described in http://www.secg.org/sec2-v2.pdf.

The cryptol verification software has been used to find bugs in the implementation of a Elliptic Curve Crypto implementations. Implementation errors can dramatically impact security properties of crypto that appears mathematically sound.

Note that a Group sounds like a simpler structure than a Field, but a Galois Group is a more complex structure than a Galois Field. https://www.encyclopediaofmath.org/index.php/Permutation_group https://math.stackexchange.com/questions/45893/how-to-find-the-galois-group-of-a-polynomial