On-the-fly modifications of the links according to

I have an HTML page with loads of entries like this:

<a href="https://www.example.co.uk/gp/wine/product?ie=UTF8&amp;asin=123456789&amp;tab=UK_Default" class="PrmryBtnMed"

I want to replace all this links so they instead are:

https://www.example.co.uk/gp/wine/order?ie=UTF8&asin=1233456789

So, it's quite a complicated search and replace. These are the instructions for a human:

Look at the URL. Only make a note of the number after 'asin='. (Forget everything before that and everything after that)
Then, form a new URL, using this ASIN. It will ALWAYS start like this: https://www.example.co.uk/gp/wine/order?ie=UTF8&asin=

With the number stuck on the end to form:

https://www.example.co.uk/gp/wine/order?ie=UTF8&asin=123456789

Kindly note

rather than modifying the existing buttons, it would also be acceptable to add a new button [or link] near the original buttons
both the original and new links point to the same domain
I'm using Greasekit on a SSB called FluidApp, but I can switch to Greasemonkey on FireFox.

I've just watched 40 JavaScript tutorial videos - man this language is hard! This seems extremely difficult. I would hugely appreciate any help/pointers.

Something like this might work:

// the new base url
var base = ' https://www.example.co.uk/gp/wine/order?ie=UTF8&asin=';
// all the links with className 'PrmryBtnMed'
var links  = document.getElementsByTagName('a');

for(var i = 0;i < links.length;i++){
    // check each link for the 'asin' value
    var result = /asin=([\d\w]+)/.exec(links[i].getAttribute('href'));
    if(result){
        // make a new url using the 'base' and the 'asin' value
        links[i].setAttribute('href', base+result[1]);
    }
}

Demo: http://jsfiddle.net/louisbros/L8ePL/